Initiate

/*
设当前已经求出的最长上升子序列长度为len。先判断s[i]与a[len]。若a[len]<=s[i]，
则将s[i]接在a[len]后将得到一个更长的上升子序列，len = len + 1，a[len]=s[i]；
否则，在a[1]..a[len]中，找到最大的j，满足a[j] <= s[i]。令k = j + 1，则有a[j] <= s[i] <= a[k]，
将s[i]接在a[j]后将得到一个更长的上升子序列，同时更新a[k] =s[i]。
最后，len即为所要求的最长上升子序列的长度。
a[]在算法结束后记录的并不是一个符合题意的最长上升子序列
它只是存储的对应长度LIS的最小末尾。
有了这个末尾，我们就可以一个一个地插入数据。
*/

 1int n,a[MAXN],s[MAXN];//序列存在s里
 2int lis()//单调不降子序列nlogn算法 
 3{
 4    int l,r,mid,len=1;
 5    a[1]=s[1];
 6    for(int i=2;i<=n;i++)
 7    {
 8           l=1,r=len;
 9           if(a[len]<=s[i]) 
10        {
11            a[++len]=s[i];
12            continue;
13        }
14           while(l<=r)
15           {
16            mid=(l+r)>>1;
17            if(a[mid]<=s[i]) l=mid+1;//不降 
18            else r=mid-1;//二分查找 
19        }
20        a[l]=s[i];//插入
21        if(l>len) len++;//增加长度
22    }
23    return len; 
24}