पायथन में सबसे लंबे फाइबोनैचि सबसीक्वेंस की लंबाई खोजने का प्रोग्राम

मान लीजिए हमारे पास एक अनुक्रम X_1, X_2, ..., X_n है जो फाइबोनैचि-जैसा है यदि:

• n >= 3
• सभी i + 2 <= n के लिए X_i + X_{i+1} = X_{i+2}

अब मान लीजिए एक सख्ती से बढ़ता हुआ ऐरे A एक अनुक्रम बनाता है, हमें 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