题目描述
给定一个长度为N的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数N。
第二行包含N个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N≤100000,
−109≤数列中的数≤109
样例
输入样例:
7
3 1 2 1 8 5 6
输出样例:
4
二分优化
复杂度$O(nlogn)$
可以发现这题的n为100000,如果直接双重循环的话,n^2
的复杂度肯定是会炸的,所以我们换新思路:
创建一个f[]来存我们子序列里的数,
先把第一个数放进去,然后接着枚举a[i],
如果发现a[i]比f[]中的最后一个数更大,
也就是比f[len]更大,
就把它放进去,len++,
因为我们可以知道如果一开始就这样做的话,
那么我们的f[]序列肯定是单调的,
所以直接加进去即可;
那么如果我们发现a[i]比f[len]更小呢,
我们可以进行二分, 寻找f[]中比a[i]大的最小的数
然后把它换成a[i];
因为这样的话后面就有机会接更多比它大的数,
最后输出长度len就可以啦。
C++ 代码
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int a[100003],f[100002];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];f[i]=0x3f3f3f;
}
f[1]=a[1];int len=1;//先把第一个放进去;
for(int i=2;i<=n;i++)
{
if(a[i]>f[len]) f[++len]=a[i];//如果比f[len]更大;
else {
int l=1,r=len,mid;
while(l<r)
{
mid=(l+r)/2;
if(f[mid]>=a[i]) r=mid;
else l=mid+1;
}//二分寻找大于a[i]的最小数;
f[l]=min(a[i],f[l]);
}
}
cout<<len;
return 0;//一个好习惯。
}
QAQ说错了求指点