显然n^2在比赛中是没有什么用的(不会这么容易就过的),所以nlogn的算法尤为重要。
分析:
开2个数组,一个a记原数,f[k]表示长度为f的不下降子序列末尾元素的最小值,tot表示当前已知的最长子序列的长度
考虑进来一个数a[i],
1.如果a[i]>=f[tot],那么接上去即可
2。如果这个元素小于f[tot]呢?说明它不能接在最后一个后面了。那我们就看一下它该接在谁后面。
准确的说,并不是接在谁后面。而是替换掉谁。因为它接在前面的谁后面都是没有意义的,再接也超不过最长的tot,所以是替换掉别人。那么替换掉谁呢?就是替换掉那个最该被它替换的那个。也就是在f数组中第一个大于它的。第一个意味着前面的都小于等于它。假设第一个大于它的是f[j],说明f[1..j-1]都小于等于它,那么它完全可以接上f[j-1]然后生成一个长度为j的不下降子序列,而且这个子序列比当前的f[j]这个子序列更有潜力(因为这个数比f[j]小)。所以就替换掉它就行了,也就是f[j]=a[i]。其实这个位置也是它唯一能够替换的位置(前面的替了不满足f[k]最小值的定义,后面替换了不满足不下降序列)
查找过程:二分(nlogn)
#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<cstdlib> int n,tot=1,a[500000],f[500000]; int find(int m,int num){ int l=1,r=m,max; while(r>=l){ int mid=(l+r)>>1; if(num>=f[mid]) l=mid+1; else{ r=mid-1; max=mid; } } return max; } int main(){ scanf("%d",&n); if(n==0){ puts("0"); return 0; } for(int i=1;i<=n;i++) scanf("%d",&a[i]); f[1]=a[1]; for(int i=2;i<=n;i++){ if(a[i]>=f[tot]) f[++tot]=a[i]; else f[find(tot,a[i])]=a[i]; } printf("%d",tot); return 0; }