Chương trình tìm độ dài dãy con Fibonacci dài nhất trong Python

Mô tả bài toán

Một dãy X_1, X_2, ..., X_n được gọi là dãy kiểu Fibonacci nếu:

n >= 3
X_i + X_{i+1} = X_{i+2} với mọi i + 2 <= n

Cho một mảng A tăng chặt chứa các số nguyên, hãy tìm độ dài của dãy con kiểu Fibonacci dài nhất của A. Nếu không tồn tại dãy nào, trả về 0.

Ví dụ

Nếu đầu vào là A = [1,2,3,4,5,6,7,8], thì đầu ra sẽ là 5 vì tồn tại dãy [1,2,3,5,8] có độ dài 5.

Giải thuật

Tạo tập hợp sA từ các phần tử của A.
Lấy last là phần tử cuối cùng của A.
Tạo bản đồ B lưu trữ tần suất xuất hiện của từng cặp (a, b).
Khởi tạo best = 0.
Duyệt i từ cuối mảng về đầu:
- Gán a = A[i].
- Duyệt b qua mảng con A[i+1:]:
  - Tính c = a + b.
  - Nếu c nằm trong sA:
    - Cập nhật B[a,b] = 1 + B[b,c].
    - Cập nhật best = max(best, B[a,b] + 2).
  - Ngược lại nếu c > last, thoát khỏi vòng lặp nội bộ.
Trả về best.

Triển khai Python

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

Đầu vào