Chương trình tìm độ dài của dãy Fibonacci dài nhất từ ​​một danh sách nhất định bằng Python

Giả sử chúng ta có một danh sách các số dương tăng dần được gọi là nums. Chúng ta phải tìm độ dài của dãy con dài nhất A (độ dài tối thiểu 3) sao cho A [i] =A [i - 1] + A [i - 2] với mọi i> 1.

Vì vậy, nếu đầu vào là nums =[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14], thì đầu ra sẽ là 6, như chúng ta có thể chọn [1, 2, 3, 5, 8, 13].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• A:=nums
• n:=kích thước của A
• maxLen:=0
• S:=một tập hợp mới từ A
• đối với tôi trong phạm vi từ 0 đến n, thực hiện
  • đối với j trong phạm vi i + 1 đến n, thực hiện
    • x:=A [j]
    • y:=A [i] + A [j]
    • chiều dài:=2
    • trong khi y hiện diện trong S, hãy thực hiện
      • z:=x + y
      • x:=y
      • y:=z
      • length:=length + 1
      • maxLen:=tối đa của maxLen, chiều dài
• nếu maxLen> 2, thì
  • trả về maxLen
• nếu không,
  • trả về 0

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

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

Đầu ra

6