求最长递增子序列

//从下标0开始
int a[maxn];//原数组
int b[maxn];//求得递增数组
int main()
{
    int cnt=1;//所求长度
    b[0]=a[0];
    for(int i=1;i<n;i++){
        if(a[i]>b[cnt-1])
            b[cnt++]=a[i];
        else{
            int pos=upper_bound(b,b+cnt,a[i])-b;
            b[pos]=min(b[pos],a[i]);
        }
    }
}

算法时间复杂度：nlog(n)