在Python中查找最长斐波那契子序列长度的程序
假设我们有一个像X_1,X_2,...,X_n这样的序列,如果-
n>=3
X_i+X_i+1=X_i+2对于所有i+2<=n
现在假设一个严格递增的数组A形成一个序列,我们必须找到A的最长类斐波那契子序列的长度。如果没有这样的序列,则返回0。
所以,如果输入像A=[1,2,3,4,5,6,7,8],那么输出将是5,因为有一个序列[1,2,3,5,8]长度5。
示例
让我们看看以下实现以获得更好的理解-
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