最長上升子序列問題(LIS):

一個數的序列bi，當b1 < b2 < ... < bS的時候，我們稱這個序列是上升的。對于給定的一個序列(a1, a2, ..., aN)，我們可以得到一些上升的子序列(子序列可以理解為：刪除0個或多個，其它數的順序不變)如：(ai1, ai2, ..., aiK)，這里1 <= i1 < i2 < ... < iK <= N。比如，對于序列(1,6,2,3,7,5)，有它的一些上升子序列，如(1,2,3,5)或者(1，6，7)等等，但前者更長。

這題目是經典的DP題目，也可叫作LIS（Longest Increasing Subsequence）最長上升子序列 或者 最長不下降子序列。很基礎的題目，有兩種算法，復雜度分別為O(n*logn)和O(n^2) 。

分析：

如何把這個問題分解成子問題呢？經過分析，發現 “求以ak（k=1, 2, 3…N）為終點的最長上升子序列的長度”是個好的子問題――這里把一個上升子序列中最右邊的那個數，稱為該子序列的“終點”。雖然這個子問題和原問題形式上并不完全一樣，但是只要這N個子問題都解決了，那么這N個子問題的解中，最大的那個就是整個問題的解。

由上所述的子問題只和一個變量相關，就是數字的位置。因此序列中數的位置k 就是“狀態”，而狀態 k 對應的“值”，就是以ak做為“終點”的最長上升子序列的長度。這個問題的狀態一共有N個。狀態定義出來后，轉移方程就不難想了。假定MaxLen (k)表示以ak做為“終點”的最長上升子序列的長度，那么：

MaxLen (1) = 1

MaxLen (k) = Max { MaxLen (i)：1<i < k 且 ai < ak且 k≠1 } + 1

這個狀態轉移方程的意思就是，MaxLen(k)的值，就是在ak左邊，“終點”數值小于ak，且長度最大的那個上升子序列的長度再加1。因為ak左邊任何“終點”小于ak的子序列，加上ak后就能形成一個更長的上升子序列。

實際實現的時候，可以不必編寫遞歸函數，因為從 MaxLen(1)就能推算出MaxLen(2)，有了MaxLen(1)和MaxLen(2)就能推算出MaxLen(3)……

代碼隨后貼出……

總結

以上是生活随笔為你收集整理的最长上升子序列问题 (LIS)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。