मान लीजिए हमारे पास एक अनुक्रम है X_1, X_2, ..., X_n फाइबोनैकी जैसा है यदि -
-
n>=3
-
X_i + X_{i+1} =X_{i+2} सभी के लिए i + 2 <=n
अब मान लें कि एक अनुक्रम बनाने वाले सकारात्मक पूर्णांकों की एक सख्ती से बढ़ती हुई सरणी ए, हमें ए के सबसे लंबे फाइबोनैकी-जैसे अनुक्रम की लंबाई ढूंढनी है। यदि कोई अस्तित्व में नहीं है, तो 0 लौटाएं। इसलिए यदि संख्या [1,2 की तरह है ,3,4,5,6,7,8], तो आउटपुट 5 होगा। फिबोनाची का सबसे लंबा अनुक्रम [1,2,3,5,8] जैसा है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
रिट:=0
-
एक नक्शा बनाएं m, n :=सरणी A का आकार
-
n x n आकार का dp नामक एक मैट्रिक्स बनाएं
-
मैं के लिए 0 से n - 1 की सीमा में
-
एम [ए [i]]:=मैं
-
j के लिए i-1 की श्रेणी में, 0 से नीचे
-
अनुरोध:=ए[i] – ए[जे]
-
जब 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 :=अधिकतम रिट और dp[i,j]
-
-
-
रिटर्न रिट जब रिट> =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