连续上升子序列（LIS）
定义
\(一个序列中单调不减的子序列或单调递增的子序列（看题决定，做法几乎一致），下文以严格上升子序列为例\)
做法一
\(暴力dp,设f_i表示以i结尾的LIS的最长长度,f_i=max(f_j|j<i ,a_j<a_i)+1。\)
\(dp比较好理解,就是由上一个比当前小的数加上当前的数组成最长上升子序列\)
\(复杂度显然是O(n^2)的\)
做法二
\(考虑去优化上述转移方程，发现f_i是由1\sim i-1转移来的，可以用树状数组优化。\)
\(每次求完f_i对a_i进行单点加，求f_i时查1 \sim a_i-1的最大值\)
\(a_i比较大时记得离散化\)
\(复杂度降为O(nlogn)\)
标签：浅谈,复杂度,sim,LIS,序列,dp From： https://www.cnblogs.com/cdx1221/p/17654765.html