Python程式：查詢給定列表中最長斐波那契子序列的長度

假設我們有一個嚴格遞增的正數列表，稱為nums。我們必須找到最長子序列A（長度至少為3）的長度，使得對於所有i > 1，A[i] = A[i - 1] + A[i - 2]。

因此，如果輸入類似於nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]，則輸出將為6，因為我們可以選擇[1, 2, 3, 5, 8, 13]。

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

  • A := nums
  • n := A的長度
  • maxLen := 0
  • S := 從A建立的新集合
  • 對於範圍0到n中的i，執行：
    • 對於範圍i + 1到n中的j，執行：
      • x := A[j]
      • y := A[i] + A[j]
      • length := 2
      • 當y存在於S中時，執行：
        • z := x + y
        • x := y
        • y := z
        • length := length + 1
        • maxLen := maxLen和length中的最大值
  • 如果maxLen > 2，則
    • 返回maxLen
  • 否則，
    • 返回0

讓我們看看下面的實現，以便更好地理解：

示例

線上演示

class Solution:
   def solve(self, nums):
      A = nums
      n = len(A)
      maxLen = 0
      S = set(A)
      for i in range(0, n):
         for j in range(i + 1, n):
            x = A[j]
            y = A[i] + A[j]
            length = 2
            while y in S:
               z = x + y
               x = y
               y = z
               length += 1
               maxLen = max(maxLen, length)
      if maxLen > 2:
         return maxLen
      else:
         return 0
ob = Solution()
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
print(ob.solve(nums))

輸入

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

輸出

6

更新於：2020年11月19日

298 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告