思路
- 如果用以下做法,时间复杂度为 $O(N^2)$ ,会 $TLE$ .
-
采用贪心思想,对于不同长度的子序列,存下最后一个数字的最小值,用数组 $q$ 来存。$q[i]$ 表示所有长度为 $i$ 的子序列中最后一个数字最小值为 $q[i]$ 。一定有 $q[i]$ 中的数字单调递增。
-
对于$num$ 数组中的第 $i$ 个数,用二分方法在 $q$ 数组中找到小于 $num[i]$ 的最大值,那么末尾为 $num[i]$ 的最长序列长度就可以得到了。
-
时间复杂度为 $O(NlogN)$ ,空间复杂度为 $O(N)$ 。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=100010,INF=0x3f3f;
int num[N];
int q[N];
int binary(int l,int r,int x){
if(q[r]<x){
return r;
}
int mid=(l+r)/2;
if(q[mid]<x&&q[mid+1]>=x){
return mid;
}else if(q[mid]<x){
return binary(mid+1,r,x);
}else{
return binary(l,mid-1,x);
}
}
int main(void){
int n,i,ans=0;
scanf("%d",&n);
memset(q,INF,sizeof q);
for(i=1;i<=n;i++){
scanf("%d",&num[i]);
}
q[0]=-q[0];
for(i=1;i<=n;i++){
int t=binary(0,i-1,num[i])+1;
q[t]=min(q[t],num[i]);
ans=max(ans,t);
}
printf("%d\n",ans);
return 0;
}