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

假設我們有一個序列X_1, X_2, ..., X_n，如果滿足以下條件，則稱其為斐波那契式序列：

  • n >= 3

  • 對於所有i + 2 <= n，都有X_i + X_i+1 = X_i+2

現在假設一個嚴格遞增的陣列A構成一個序列，我們需要找到A中最長斐波那契式子序列的長度。如果沒有這樣的序列，則返回0。

例如，如果輸入為A = [1,2,3,4,5,6,7,8]，則輸出為5，因為存在長度為5的序列[1,2,3,5,8]。

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

  • sA := 從A的元素建立一個新的集合

  • last := A的最後一個元素

  • B := 一個對映，包含A中存在的每個元素及其頻率

  • best := 0

  • for i in A的長度 從後往前迴圈, do

    • a := A[i]

    • for each b in A的子陣列（從索引i+1到結尾）, do

      • c := a+b

      • if c 存在於 sA 中, then

        • B[a,b] := 1 + B[b,c]

        • best := best 和 B[a,b]+2 的最大值

      • otherwise when c > last, then

        • 退出迴圈

  • return best

示例

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

from collections import Counter
def solve(A):
   sA = set(A)
   last = A[-1]
   B = Counter()
   best = 0
   for i in reversed(range(len(A))):
      a = A[i]
      for b in A[i+1:]:
         c = a+b
         if c in sA:
            B[a,b] = 1 + B[b,c]
            best = max(best , B[a,b]+2)
         elif c>last:
            break
   return best

A = [1,2,3,4,5,6,7,8]
print(solve(A))

輸入

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

輸出

5

更新於：2021年10月7日

瀏覽量：146

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告