最长上升子序列（Longest Increasing Subsequence，LIS）

最长上升子序列（Longest Increasing Subsequence，LIS）
简单的动态规划思路是对于每一个数字都是一个状态 然后处理每一个状态的时候 要遍历前面的状态满足
d(i)=max{0,d(i)|j<i,Aj<Ai}+1,最后的结果就是选出Aj<Ai为前提的最大d（j）再加上一
因为每一个都要遍历前面的状态 所以时间复杂度为n^2


现在要学习一种时间复杂度为nlongn的算法
其实这个优化方法使用了二分查找的方法 使用一个数组 坐标是从1开始的 d[i] ，i代表的是现在子序列的长度 d[i]是代表该子序列最后一个数的值 
因为同一个长度的子序列有很多个 但是d[i]代表的的相同长度子序列最小的最后一个数的值
貌似有以下几个操作
   1.如果比数组最后一个数值还要大 直接放在最后一个数的后面，即d[i+1]=x
   2.如果这个数比第一个还要小的话就直接跳过（不过有一个特殊情况当只有一个数的时候是不能这样做的）
   3.如果这个数介于两个数之间 那么这个数就取代后面的数






/* 
    HDU 1950 Bridging signals 
            -----最长上升子序列nlogn算法 
*/  
  
#include<cstdio>  
#include<cstring>  
#define MAXN 40005  
  
int arr[MAXN],ans[MAXN],len;  
  
/*  
    二分查找。 注意，这个二分查找是求下界的;  (什么是下界？详情见《算法入门经典》 P145) 
    即返回 >= 所查找对象的第一个位置（想想为什么） 
 
    也可以用STL的lowe_bound二分查找求的下界 
*/  
  
int binary_search(int i){  
    int left,right,mid;  
    left=0,right=len;  
    while(left<right){  
        mid = left+(right-left)/2;  
        if(ans[mid]>=arr[i]) right=mid;  
        else left=mid+1;  
    }  
    return left;  
}  
  
int main()  
{  
    freopen("input.txt","r",stdin);  
    int T,p,i,j,k;  
    scanf("%d",&T);  
    while(T--){  
        scanf("%d",&p);  
        for(i=1; i<=p; ++i)  
            scanf("%d",&arr[i]);  
          
        ans[1] = arr[1];  
        len=1;  
        for(i=2; i<=p; ++i){  
            if(arr[i]>ans[len])  
                ans[++len]=arr[i];  
            else{  
                int pos=binary_search(i);   // 如果用STL： pos=lower_bound(ans,ans+len,arr[i])-ans;   
                ans[pos] = arr[i];  
        }  
        printf("%d\n",len);  
    }  
    return 0;  
}  






这里的代码处理有一个小技巧 就是数值放的数字是从1开始的 但是left是从0开始的 这样就处理掉操作2 还有特殊的情况 因为数组0那里就是用来放数的