Chương trình tìm độ dài dãy con Fibonacci dài nhất từ danh sách cho trước trong Python

Mô tả bài toán

Cho danh sách nums tăng chặt các số dương. Tìm độ dài dãy con dài nhất (tối thiểu 3) thỏa mãn A[i] = A[i-1] + A[i-2] cho mọi i > 1.

Ví dụ: nums = [1,2,3,4,5,6,7,8,9,10,11,12,13,14] → đầu ra 6 (dãy [1,2,3,5,8,13]).

Giải thuật (Thử tất cả cặp khởi đầu + Set tra cứu)

1. Đưa tất cả phần tử vào tập hợp S.
2. Duyệt mọi cặp (i, j) với i < j:
   • x = nums[j], y = nums[i] + nums[j], length = 2.
   • Trong khi y in S: z = x + y, x = y, y = z, length += 1, cập nhật maxLen.
3. Trả về maxLen nếu > 2, ngược lại 0.

Ví dụ mã 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))

Đầu vào

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

Đầu ra

6