ধরুন আমাদের একটি ক্রম আছে X_1, X_2, ..., X_n হল ফিবোনাচির মত যদি −
-
n>=3
-
X_i + X_{i+1} =X_{i+2} সমস্ত i + 2 <=n
এর জন্য
এখন ধরুন ধনাত্মক পূর্ণসংখ্যাগুলির একটি কঠোরভাবে ক্রমবর্ধমান অ্যারে একটি ক্রম তৈরি করে, আমাদের A এর দীর্ঘতম ফিবোনাচি-সদৃশ অনুক্রমের দৈর্ঘ্য খুঁজে বের করতে হবে। যদি একটি বিদ্যমান না থাকে, তাহলে 0 ফেরত দিন। তাই যদি সংখ্যাটি [1,2' এর মত হয় ,3,4,5,6,7,8], তাহলে আউটপুট হবে 5। দীর্ঘতম অনুবর্তন যা ফিবোনাচি হল [1,2,3,5,8] এর মত।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ret :=0
-
একটি মানচিত্র তৈরি করুন m, n :=অ্যারের আকার A
-
n x n
আকারের dp নামে একটি ম্যাট্রিক্স তৈরি করুন -
0 থেকে n – 1
রেঞ্জের i জন্য-
m[A[i]] :=i
-
j এর জন্য রেঞ্জ i – 1, নিচে 0
-
req :=A[i] – A[j]
-
যখন A[i] – A[j]
-
dp[i, j] :=সর্বাধিক dp[i, j], dp[j, m[A[i] – A[j]]] + 1
-
-
অন্যথায় dp[i,j] :=সর্বাধিক dp[i, j] এবং 2
-
ret :=ret এবং dp[i,j]
এর সর্বোচ্চ
-
-
-
রিটার্ন ret যখন ret>=3 অন্যথায় 0 ফেরত দিন।
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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
