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

假设我们有一个严格递增的正数列表，称为nums。我们必须找到最长子序列A（长度至少为3）的长度，使得对于所有i > 1，A[i] = A[i - 1] + A[i - 2]。

因此，如果输入类似于nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]，则输出将为6，因为我们可以选择[1, 2, 3, 5, 8, 13]。

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

  • A := nums
  • n := A的长度
  • maxLen := 0
  • S := 从A创建的新集合
  • 对于范围0到n中的i，执行：
    • 对于范围i + 1到n中的j，执行：
      • x := A[j]
      • y := A[i] + A[j]
      • length := 2
      • 当y存在于S中时，执行：
        • z := x + y
        • x := y
        • y := z
        • length := length + 1
        • maxLen := maxLen和length中的最大值
  • 如果maxLen > 2，则
    • 返回maxLen
  • 否则，
    • 返回0

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

示例

在线演示

class Solution:
   def solve(self, nums):
      A = nums
      n = len(A)
      maxLen = 0
      S = set(A)
      for i in range(0, n):
         for j in range(i + 1, n):
            x = A[j]
            y = A[i] + A[j]
            length = 2
            while y in S:
               z = x + y
               x = y
               y = z
               length += 1
               maxLen = max(maxLen, length)
      if maxLen > 2:
         return maxLen
      else:
         return 0
ob = Solution()
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
print(ob.solve(nums))

输入

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

输出

6

更新于：2020年11月19日

298 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告