পাইথনে সবচেয়ে দীর্ঘ ফিবোনাচি সাবসিকোয়েন্সের দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম

মান লেন একটি সিকোয়েন্স X₁, X₂, ..., Xₙ ফিবোনাচি-সদৃশ যদি:

n ≥ 3
সব i + 2 ≤ n এর জন্য Xᵢ + Xᵢ₊₁ = Xᵢ₊₂

এখন একটি স্ট্রিক্টলি ক্রমবর্ধমান অ্যারে A দেওয়া আছে, আমাদের এর সবচেয়ে দীর্ঘ ফিবোনাচি-সদৃশ সাবসিকোয়েন্সের দৈর্ঘ্য খুঁজে বের করতে হবে। যদি এমন কোনো সিকোয়েন্স না থাকে, তবে 0 রিটার্ন করুন।

উদাহরণস্বরূপ, ইনপুট A = [1,2,3,4,5,6,7,8] হলে আউটপুট হবে 5 কারণ [1,2,3,5,8] সিকোয়েন্সটির দৈর্ঘ্য 5।

সমাধানের ধাপসমূহ

sA := A-এর উপাদানlardan একটি সেট তৈরি করুন
last := A-এর শেষ উপাদান
B := A-এ উপস্থিত প্রতিটি উপাদান এবং তাদের ফ্রিকোয়েন্সি ধারণকারী একটি ম্যাপ
best := 0
i = A-এর আকার থেকে 0 পর্যন্ত লুপ চালান:
- a := A[i]
- A[i+1] থেকে শেষ পর্যন্ত সাবঅ্যারের প্রতিটি b এর জন্য:
  - c := a + b
  - যদি c sA-তে থাকে, তবে:
    - B[a,b] := 1 + B[b,c]
    - best := max(best, B[a,b] + 2)
  - অন্যথায়, যদি c > last হয়, তবে:
    - লুপ থেকে বেরিয়ে আসুন
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]