最長遞增子序列問題

• 簡述

  • 經典的動態規劃問題。

• 問題描述

  • 給定一個序列，求解其中長度最長的遞增子序列。

• 問題分析

  • 這種可以向下查詢答案的很容易想到動態規劃的解法。
  • 要求長度為i的序列Ai={a1,a2,a3,ai}的最長遞增子序列，需要先求出序列Ai-1{a1,a2,a3,ai-1}中各元素(a1,a1,ai-1)作為最大元素的最長遞增子序列，然后將這i-1個遞增序列與ai進行比較。如果某個長度為m的序列的末尾元素aj(j<i)比ai小，則將元素ai加入這個遞增子序列，得到一個長度為m+1的新序列，否則其長度不變，將處理后的i-1個序列的長度進行比較，最長的就是要求的最長遞增子序列。
  • 舉個例子
    • 對于序列A{3,1,4,5,9,2,6,5,0}，當處理到第7個元素“6”時，i-1個序列為。
      • 3
      • 1
      • 3,4
      • 3,4,5
      • 3,4,5,9
      • 1,2
    • 經過上述處理后，序列變為如下。有兩個最長的。可見，以“6”為結尾的最長遞增子序列為{3,4,5,6}。
      • 3,6
      • 1,6
      • 3,4,6
      • 3,4,5,6
      • 3,4,5,9
      • 1,2,6
    • 同樣，處理到第8個元素“5”的時候，原始序列處理后變為如下。
      • 3,5
      • 1,5
      • 3,4,5
      • 3,4,5
      • 3,4,5,9
      • 1,2,5
    • 可見，以第8個元素“5”為結尾的最長遞增子序列為{3,4,5}。
    • 最后一個0，無法在后面添加，因此，這個題目的答案為{3,4,5,9}。序列A的最長遞增子序列長度為4.
    • 注意：求解到的最長遞增子序列可能不止一個。
  • 設f(i)表示序列中以ai為末尾元素的最長遞增子序列的長度，則在求以ai為末尾元素的最長遞增子序列是，找到所有序號在i前面且小于ai的元素aj，即j<i且aj<ai。
    • 如果這樣的元素存在，那么對所有的aj，都有一個以aj為末尾元素的最長遞增子序列的長度f(j)。把其中最大的f(j)找出來，f(i)就等于這個最大的f(j)+1。也就是說，以ai為末尾元素的最長遞增子序列，等于在使f(j)最大的那個aj為末尾元素的遞增子序列最后再加上ai；如果這樣的元素不存在，那么自身構成一個長度為1的以ai為末尾元素的遞增子序列。

• 代碼

  • def f(arr):n = len(arr)dp = [0] * nfor i in range(n):dp[i] = 1for j in range(i):if arr[j] < arr[i]:dp[i] = max(dp[i], dp[j]+1)return dpdef generate_lis(arr, dp):n = max(dp)index = dp.index(n)lis = [0] * nn -= 1lis[n] = arr[index]# 從右向左查for i in range(index, -1, -1):if arr[i] < arr[index] and dp[i] == dp[index] - 1:n -= 1lis[n] = arr[i]index = ireturn lisif __name__ == '__main__':arr = [3, 1, 4, 5, 9, 2, 6, 5, 0]print(generate_lis(arr, f(arr)))
  • 這種不確定向下查找的方向的不適合使用遞歸。

• 算法改進

  • 上面那種解法的復雜度達到了O(n^2)，其實可以改進為O(nlogn)。
  • 在基本算法中，當需要計算前i個元素的最長遞增子序列的時候，前i-1個元素作為最大元素的i-1個遞增序列，無論是長度，還是最大元素值，都毫無規律，所以在開始計算前i個元素的時候只能遍歷前i-1個元素，以找到滿足的j值，使得aj<ai且滿足條件的j中，以aj作為最大元素的遞增子序列最長。
  • 其實。在一個序列中，長度為n的遞增子序列可能不只有一個，但是最大元素最小的遞增子序列只有一個。上面例子中，當處理第7個元素“6“時，長度為2的子序列有兩個，即{3,4}和{1,2}，這個{1,2}就是最大元素最小的遞增子序列。（可以輕易證明唯一性）隨著序列長度的變化，滿足條件的子序列不斷變化。
  • 如果將這些子序列安裝長度由短到長排序，將每個序列的最大元素放在一起，形成新序列B{b1,b2,bj},則序列B一定是遞增的。（此處不證明）
  • 發現了這個嚴格遞增，眼前一亮，可以利用此序列的嚴格遞增進行二分查找，找到最大元素剛好小于aj的元素bk，將aj加入這個序列尾部，形成長度為k+1但是最大元素又小于b(k+1)的新序列，取代之前的b(k+1)。如果aj比B中所有元素都大，說明發現了以aj為最大元素，長度為n+1的遞增序列，將aj作為B(n+1)的第n+1個元素。從b1依次遞推，可以在O(nlogn)時間內找出A的最長遞增子序列。
  • 這種方法大幅度提高了運行效率。
  • 優化代碼見我的Github

• 補充說明

  • 具體代碼可以查看我的Github，歡迎Star或者Fork
  • 參考書《你也能看得懂的Python算法書》，書中略微有一點不合理之處，做了修改
  • 到這里，其實你已經體會到了動態規劃的簡約之美，當然，要注意Python是有遞歸深度限制的，如不是必要，建議使用循環控制

總結

以上是生活随笔為你收集整理的动态规划算法-04最长递增子序列问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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