用了O(n^2)的方法会超时…
所以学习了另一种O(nlogn)的方法：

纯说一些东西有点抽象，所以还是举个栗子：

定义d[k]:长度为k的上升子序列的最末元素，若有多个长度为k的上升子序列，则记录最小的那个最末元素。

举例：原序列为1，5，8，3，6，7

栈为1，5，8，此时读到3，用3替换5，得到1，3，8； 再读6，用6替换8，得到1，3，6；再读7，得到最终栈为1，3，6，7。最长递增子序列为长度4。

找位置的时候就可以用到二分啦…

这里还用到了lower_bound函数(从已经排好序的的序列a中利用二分搜索找出指向满足ai>=k的最小的指针。类似的函数还有upper_bound，这一函数求出的是指向ai>k的ai的最小的指针。长度为n的有序数组a中k的个数，可以用upper_bound(a,a+n,k)-lower_bound(a,a+n,k)求出)

#define INF 0x3f3f3f3f
int a[50100];
int dp[50100];
int main()
{
    int n,i,loc,len;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    fill(dp,dp+n,INF);
    len=0;
    for(i=0;i<n;i++)
    {
        loc=lower_bound(dp,dp+len,a[i])-dp;
        dp[loc]=a[i];
        if(loc==len)len++;
    }
    printf("%d\n",len);
    return 0;
}