显然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=,a[],f[];
int find(int m,int num){
int l=,r=m,max;
while(r>=l){
int mid=(l+r)>>;
if(num>=f[mid])
l=mid+;
else{
r=mid-;
max=mid;
}
}
return max;
}
int main(){
scanf("%d",&n);
if(n==){
puts("");
return ;
}
for(int i=;i<=n;i++) scanf("%d",&a[i]);
f[]=a[];
for(int i=;i<=n;i++){
if(a[i]>=f[tot]) f[++tot]=a[i];
else f[find(tot,a[i])]=a[i];
}
printf("%d",tot);
return ;
}