在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创建一个新的集合
• 对于i在范围0到n内，执行以下操作
  • 对于j在范围i + 1到n内，执行以下操作
    • x：= A [j]
    • y：= A [i] + A [j]
    • 长度：= 2
    • 当y存在于S中时，执行以下操作
    • z：= x + y
    • x：= y
    • y：= z
    • 长度：=长度+ 1
    • maxLen：= max（maxLen，length）
• 如果maxLen > 2，则返回maxLen
  • • 否则，返回0

下面是一个实现示例，以便更好地理解-

更多Python相关文章，请阅读：Python 教程

例子

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