今天看了hdu的1159，以为是最长递增子序列，然后敲完代码发现samp不对，看了discuss发现原来是lcs
最长递增子序列（LIS）：求一个序列的LIS
有三种算法，一种是排个序然后和自己求最长公共子序列
第二种就是dp，dp[i] = max(dp[j]) + 1; (j∈[0,i-1]),dp[i]表示前i个的LIS的长度，能用这个状态方程肯定要加个判断条件的，即保证递增
第三种就是
用一个数组B[i]，表示长度为i的结尾的最小的值
从第一个开始遇到一个新值，就在B数组里查看是否可以插进去，即是不是可以更新某个长度结尾的最小值，能更新就更新之，不能的话，那就意味着它比B数组的所有值都大
那么就代表LIS的长度又要增加一
因为B数组肯定有序，而查找替换就可以用二分解决了，因此这个算法的时间复杂度为O（nlogn）
参考：O（nlogn）算法
标签：递增,数组,LIS,序列,最长,dp From： https://blog.51cto.com/u_16192154/6767485