用LCS解決LIS問題

最長上升子序列有它的套路，不過用LCS算法是可以解決的： 假設原序列為A$A$ 第一步：現在對原序列進行排序得到排序后的序列B$B$ 第二步：考慮原序列A$A$可能有重復元素，對序列B$B$還要進行去重得到序列B′$B^{'}$ 第三步：對A$A$和B′$B^{'}$做LCS運算，即可得出原序列A$A$的LIS最長上升子序列。

好，這個算法在LeetCode是Memory Limit

代碼

LIS動態規劃

LIS還是有它的套路，比如動態規劃方程如下： dp(i)=dp(j)max+1,0≤j<i,aj<ai$dp(i)=dp(j)_{max}+1 , 0/leq j < i,a_j < a_i$ 注意這里的dp(i)$dp(i)$是一個局部最優，表示當LIS以ai$a_i$結尾時的最優，因此我們首先要從0 i?1$0~i-1$找一各滿足aj<ai$a_j < a_i$條件的局部最優，再在后面補上ai$a_i$即是當前局部最優。

有了動歸方程，再根據動歸方程算出的局部最優解求全局最優就很EZ了。