最长递增子序列……看到和别人的巨大差距了，自已写了一个DP，感觉很麻烦，再看看别人的思路，感觉豁然开朗~~
         主要想法就是边找边修改，正确性我也反应了半天，才觉得设计的很巧妙，学习学习~~
         初始时len=0，len表示当前最长序列的长度-1(从0开始)。
         从前向后扫描输入数组，在a[0]~a[len]中找到最小的比a[i]大的元素位置(如果没有就是len+1)并将此元素替换成a[i]，直到数组结尾，输出len+1。
         正确性：首先，很容易看出len<=i，因此不必另开数组，直接在原数组上操作，其次，根据替换规则，每个位置的元素都是所有该长度序列中可能的最小元素，否则可以找到一个更小的替换它，则对于最长的序列，它的长度不会缩短，而且由于是顺序扫描，最长序列的长度不会因为替换而增加，即不存在一种情况，使得把第i个元素替换后，导致原本不属于最长序列的元素加入到最长序列中来，否则，把该元素和前i个元素及最长序列的i+1~len个元素组成新的最长序列，与假设最长序列矛盾。
         故此算法产生的序列第i个元素为所有长度不小于i的序列的第i个位置最小元素，它的长度为最长序列的长度。
         下面是我的实现代码：

#include <iostream>
int main(){
    int n, a[40001], p, i, l, h, mid, len;
    scanf("%d",&n);
    while( n-- ){
        scanf("%d",&p);
        for( i= 0; i< p; i++ )
            scanf("%d",&a[i]);
        len= 0;
        for( i= 1; i< p; i++ ){
            if( a[i]> a[len] )
                a[++len]= a[i];
            else{
                l= 0;
                h= len;
                while( l<= h ){
                    mid= ( l+ h )/ 2;
                    if( a[i]< a[mid] ) h= mid- 1;
                    else l= mid+ 1;
                }
                a[l]= a[i];
            }
        }
        printf("%d\n",len+1);
    }
    return 0;
}