最长上升子序列_alaso_shuang的博客-爱代码爱编程
最长上升子序列
两道模板题,体验时间复杂度带来的快感以及方法不同的乐感!
AcWing 895. 最长上升子序列
AcWing 896. 最长上升子序列 II
我们用a[i]表示原序列,f[i]是记录这个数的值是多少!
而后递推一下子就出来了
对于不懂如何递推的话请看下图:
可以自己模拟一下
代码中的f[i] = 1是指我把f[ ]里里面的值全设为1
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1020;
int a[N],f[N];
int n;
int main()
{
int ans = 1;
cin>>n;
for(int i = 1;i <= n;i++)cin>>a[i];
for(int i = 1;i <= n;i++)
{
f[i] = 1;
for(int j = 1;j < i;j++)
if(a[i] > a[j])f[i] = max(f[i],f[j]+1);
ans = max(ans,f[i]);
}
cout<<ans<<endl;
return 0;
}
Ps:学东西要学透不是吗
我们想想上面这个dp状态的时间复杂度为 O(n ^ 2)时间开销是不是很大?
于是我们得想另外的办法降低时间复杂度对吧
二分查找方法
二分查找的时间复杂度是O(nlogn)所以对于数据大一点的来讲,这个方法不会出错!!
例题请看:
数据范围变了一下而已
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int a[N],f[N];//f[]记录上升子序列,表示有序数列
int len;//上升子序列的长度
int find(int x)//二分查找第一个大于等于x的位置
{
int l = 1,r = len,mid;
while(l <= r)
{
mid = (l+r)>>1;
if(x > f[mid]) l = mid+1;
else r = mid-1;
}
return l;
}
//也不是不可以用lower_bound( )
int main()
{
cin>>n;
int j;
len = 1;
for(int i = 1;i <= n;i++)cin>>a[i];
f[1] = a[1];
//考虑新加进来的a[i]
for(int i = 2;i <= n;i++)
{
//大于则添加
if(a[i] > f[len]) f[++len] = a[i];
else//小于等于则替换
{
j = find(a[i]);
f[j] = a[i];
}
}
cout<<len<<endl;
return 0;
}