Python程序：查找最长的斐波那契子序列的长度

假设我们有一个序列X_1，X_2，…，X_n，如果满足以下条件，则它是斐波那契-like

n >= 3
对于所有 i + 2 <= n，都有X_i + X_i + 1 = X_i + 2

现在假设一个严格递增的数组A形成一个序列，我们需要找到A的最长斐波那契-like子序列的长度。如果没有这样的序列，则返回0。

因此，如果输入如A = [1,2,3,4,5,6,7,8]，则输出将是5，因为有一个长度为5的序列[1,2,3,5,8]。

为了解决这个问题，我们需要按以下步骤操作：

将A的元素建立成一个新的集合sA
last := A的最后一个元素
B := 包含A中每个元素及其频率的映射
best := 0
从A大小开始向下循环到0的每个i，做如下操作
- a := A[i]
- 对于从A [从索引i + 1到结尾的子数组]的每个b，做如下操作：
  - c := a+b
  - 如果c存在于sA中，则执行以下操作
  - B [a，b] := 1 + B [b，c]
  - best := best和B [a，b] + 2的最大值
  - 否则，当c > last时，执行以下操作
  - 跳出循环
返回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在sA中：
            B [a，b] = 1 + B [b，c]
            best = max（best，B [a，b] + 2）
         elif c> last：
           退出循环
   返回best

A = [1,2,3,4,5,6,7,8]
print（solve（A））