একটি সিকোয়েন্স X₁, X₂, ..., Xₙ fibonacci-like হয় যদি -
n ≥ 3
Xᵢ + Xᵢ₊₁ = Xᵢ₊₂ সব i+2 ≤ n-এর জন্য
একটি স্ট্রিক্টলি ইনক্রিজিং পূর্ণসংখ্যা অ্যারে A দেওয়া আছে, এর মধ্যে সবচেয়ে লম্বা fibonacci-like সাবসিকোয়েন্সের দৈর্ঘ্য খুঁজে বের করতে হবে। না থাকলে ০ রিটার্ন করুন। [1,2,3,4,5,6,7,8] হলে আউটপুট ৫। সবচেয়ে লম্বা ফিবোনাচি সাবসিকোয়েন্স [1,2,3,5,8]।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
ret := 0
একটি ম্যাপ m, n := A.size()
n x n আকারের dp ম্যাট্রিক্স তৈরি করুন
i = 0 থেকে n-1 পর্যন্ত লুপ চালান
m[A[i]] := i
j = i-1 থেকে ০ পর্যন্ত ডিক্রিমেন্ট করে লুপ চালান
req := A[i] - A[j]
যদি A[i] - A[j] < A[j] এবং m-এ (A[i] - A[j]) থাকে, তবে
dp[i][j] := max(dp[i][j], dp[j][m[A[i]-A[j]]] + 1)
অন্যথায় dp[i][j] := max(dp[i][j], 2)
ret := max(ret, dp[i][j])
ret >= 3 হলে ret রিটার্ন করুন, অন্যথায় ০
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
উদাহরণ
#include <bits/stdc++.h> using namespace std; class Solution { public: int lenLongestFibSubseq(vector<int> & A) { int ret = 0; unordered_map <int, int> m; int n = A.size(); vector < vector <int> > dp(n, vector <int>(n)); for(int i = 0; i < n; i++){ m[A[i]] = i; for(int j = i - 1; j >= 0; j--){ int req = A[i] - A[j]; if(A[i] - A[j] < A[j] && m.count(A[i] - A[j])){ dp[i][j] = max(dp[i][j], dp[j][m[A[i] - A[j]]] + 1); }else{ dp[i][j] = max(dp[i][j], 2); } ret = max(ret, dp[i][j]); } } return ret >= 3 ? ret : 0; } }; main(){ vector<int> v = {1,2,3,4,5,6,7,8}; Solution ob; cout << (ob.lenLongestFibSubseq(v)); }ইনপুট
[1,2,3,4,5,6,7,8]
আউটপুট
5
