数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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
广告