尋找 Python 中最長遞增子序列長度的程式

假設我們有一系列數字。我們必須找到最長遞增子序列的長度。因此，如果輸入類似於[6, 1, 7, 2, 8, 3, 4, 5]，則輸出將為 5，因為最長的遞增子序列是[2,3,4,5,6]。

為了解決這個問題，我們將遵循以下步驟：

  • 建立一個名為 tails 的陣列，其大小與 nums 相同，並用 0 填充它。

  • size := 0

  • 對於 nums 陣列中的每個元素 x：

    • i := 0, j := size

    • 當 i 與 j 不相同時，

      • mid := i + (j – i)/2

      • 如果 tails[mid] < x，則 i := mid + 1，否則 j := mid

    • tails[i] := x

    • size := i + 1 和 size 中的最大值

  • 返回 size。

讓我們看看下面的實現以獲得更好的理解：

示例

class Solution(object):
   def solve(self, nums):
      tails =[0 for i in range(len(nums))]
      size = 0
      for x in nums:
         i=0
         j=size
         while i!=j:
            mid = i + (j-i)//2
            if tails[mid]> x:
               i= mid+1
            else:
               j = mid
         tails[i] = x
         size = max(i+1,size)
      return size

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

輸入

[7, 2, 8, 3, 9, 4, 5, 6]

輸出

5

更新於： 10-10-2020

504 次檢視

開啟你的 職業

完成課程獲得認證

開始
廣告