Python 查詢迴圈遞增子序列長度的程式

假設我們有一個名為 nums 的數字列表，我們需要查詢最長遞增子序列的長度，且假設該子序列可以環繞到列表的開頭。

因此，如果輸入類似於 nums = [6, 5, 8, 2, 3, 4]，則輸出將為 5，因為最長遞增子序列是 [2, 3, 4, 6, 8]。

為了解決這個問題，我們將按照以下步驟進行操作 -

  • a: 建立一個大小是 nums 兩倍的列表，並填充兩次 nums
  • ans: 0
  • 對於從 0 到 nums 的大小的 i，執行以下操作
    • dp: 一個新的列表
    • 對於從 i 到 nums 的大小 + i - 1 的 j，執行以下操作
      • n: a[j]
      • k: 將 n 插入 dp 的最左索引
      • 如果 k 與 dp 的大小相同時，則
        • 將 n 插入 dp 的末尾
      • 否則，
        • dp[k]:= n
      • ans: ans 的最大值和 dp 的大小
  • 返回 ans

讓我們瞭解一下以下實現，以更好地理解 -

示例 

現場演示

import bisect
class Solution:
   def solve(self, nums):
      a = nums + nums
      ans = 0
      for i in range(len(nums)):
         dp = []
         for j in range(i, len(nums) + i):
            n = a[j]
            k = bisect.bisect_left(dp, n)
            if k == len(dp):
               dp.append(n)
            else:
               dp[k] = n
         ans = max(ans, len(dp))
      return ans

ob = Solution()
nums = [4, 5, 8, 2, 3, 4]
print(ob.solve(nums))

輸入

[4, 5, 8, 2, 3, 4]

輸出

5

更新於： 03-12-2020

133 次瀏覽

開啟您的 職業生涯

完成課程獲得認證

開始
廣告