用 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，因为有一个长度为 [1,2,3,5,8] 的序列5.

为了解决这个问题，我们将遵循以下步骤 −

• sA := 来自 A 元素的新集合

• last := A 的最后一个元素

• B := 包含 A 中存在的每个元素及其频率的映射

• best := 0

• 对于 A 的大小从 0 开始的 i，执行

  • a := A[i]

  • 对于 A 子数组中的每个 b[从索引 i+1 到末尾]，执行

    • 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 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
  

  ---

  相关文章

  • Python 中通过 K 扩展列表
  • Python - 使用交替的 0 和 1 初始化列表
  • Python 中元组列表到字典的转换
  • Python - 从两个列表中配对，使得成对的元素不相同
  • 使用 Python 和 SQLite 的 SQL
  • 使用 pytrie 模块在 Python 中进行前缀匹配
  • 创建和访问 Python 包
  • 如何使用正则表达式和数据类型选择多个 DataFrame 列
  • 如何在 Pandas 中查找和过滤重复行?
  • 用 Python 编写程序以正确的顺序查找机场?

  ---

  有用资源

  • python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

  ---

  打印 下一节:用 Python 编写程序，为每个查询查找最大 XOR ❯❮ 上一节:用 Python 编写程序，查找字符串及其子字符串的总相似度