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

示例

让我们来看下面的实现，以便更好地理解：

Open Compiler
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]

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

5

更新于：2021年10月7日

浏览量：146

开启你的职业生涯

完成课程获得认证

开始学习
广告