โปรแกรมหาความยาวส่วนต่อเนื่องฟิบонаชชีสูงสุดใน Python

สมมติว่ามีลำดับ X_1, X_2, ..., X_n เรียกว่าฟิบอนาชชี-ลักษณะ (fibonacci-like) หาก:

• n >= 3
• X_i + X_{i+1} = X_{i+2} สำหรับทุก i + 2 <= n

ถ้ามีอาร์เรย์ A ที่เพิ่มขึ้นอย่างเคร่งครัด เราต้องหาความยาวของส่วนต่อเนื่อง (subsequence) แบบฟิบอนาชชีที่ยาวที่สุดของ A หากไม่มี ให้คืนค่า 0

ตัวอย่าง: A = [1,2,3,4,5,6,7,8] ผลลัพธ์คือ 5 เพราะมีลำดับ [1,2,3,5,8] ความยาว 5

วิธีแก้ปัญหา

1. sA := เซตจากองค์ประกอบของ A
2. last := องค์ประกอบสุดท้ายของ A
3. B := แมปเก็บความถี่ของแต่ละค่าใน A
4. best := 0
5. วนลูป i จากขนาดของ A ลงมา 0:
   • a := A[i]
   • วนลูป b ในสับอาร์เรย์ A[i+1:]:
     • c := a + b
     • ถ้า c อยู่ใน sA:
       • B[a,b] := 1 + B[b,c]
       • best := max(best, B[a,b] + 2)
     • มิฉะนั้นถ้า c > last ให้ออกจากลูป
6. คืนค่า best

ตัวอย่างโค้ด

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

อินพุต

[1,2,3,4,5,6,7,8]

เอาต์พุต

5