LIS问题是经典的动态规划问题，它的状态转移相信大家都很熟悉：
f[i] = f[k] + 1 (k < i 且 A[k] < A[i])
显然这样做复杂度是O(n^2)
有没有更快的算法呢？
当然，你会发现你在往前找的过程中实际上就是在查询最大值的过程，如果能应用二分就很有机会降到nlogn
但是原f[]序列并不满足二分性质呐。。怎么办呢？
我们要的是往前长度最大的，我们的二分目标就是长度
不妨开一个长度数组len[i]，表示长度为i的上升子序列最后末尾的值的最小值
对于没算出的len，设为INF，每次算完f[i]后，就对len[f[i]]进行更新
这样子我们就可以每次logn算出f[i]
为什么这样是正确的呢？
应为len[]数组是单调递增的，长度为2的末尾值一定比长度为3的要小，所以我们写的二分一定是最大值的二分
fill(len,len + maxn,INF);
len[0] = 0;
int ans = 0;
REP(i,n){
//cout<<A[i]<<' ';
int L = 0,R = ans;
while (L < R){
int mid = (L + R + 1) >> 1;
if (len[mid] < A[i]) L = mid;
else R = mid - 1;
}
f[i] = L + 1;
len[f[i]] = min(len[f[i]],A[i]);
ans = max(ans,f[i]);
}
cout<<ans<<endl;