LIS

朴素法：

//ans数组为待查询数组
void lis(int n){
    int num[n+1];
    for(int i=1;i<=n;++i)  num[i]=1;//num[i]表示从1到i的最长上升子序列的长度 
    for(int i=1;i<=n;++i){//每次加入一个ans[i],就扫描ans[1]到ans[i-1],如果ans[i]大于他们，那么num[i]就等于他们的最大长度加一，然后取最大值 
        for(int j=1;j<i;++j){
            if(ans[i]>ans[j]){
                num[i]=max(num[j]+1,num[i]);
            }
        }
    }
    for(int i=1;i<=n;++i){//找最大 
        mx=max(mx,num[i]);
    }
}

nlogn：二分

//ans数组为待排序数组
void lis(int n){
    int num[n+1];//维护一个有序数组num，最后num的长度即是最大上升子序列的长度 
    num[1]=ans[1] ;
    int len=1;
    for(int i=2;i<=n;++i){
        if(ans[i]>num[len]){
            num[++len]=ans[i];
        }
        else{//当前的ans[i]大于有序数组num的最大值 
            //从num数组中找到第一个大于等于ans[i]的数的位置 
            int tmp=lower_bound(num+1,num+len+1,ans[i])-num;
            //将找到的位置的值换成ans[i]，此时num依然有序 
            num[tmp]=ans[i];
        } 
    }
/*
列如序列：1,2,6,4,5
当n从1到3时原序列上升，对应的num数组从1到n等于ans 即1,2,6
 n==4  tmp=3   num[3]=ans[i]=4  此时num数组：1,2,4   len=3
 n==5  ans[5] =5>num[len]=4   num[5]=5   此时num数组：1,2,4,5  len=4
 ********
 这种方法并不能求出最长上升子序列本身，只能求长度
 例如原序列：1  2   4  5  3
 按此方法求出的是1  2  3  5 ，答案应该是1 2 4 5 
*/
    mx=len; 
}