एक अनुक्रम X₁, X₂, ..., Xₙ फाइबोनैचि-जैसा (fibonacci-like) होता है यदि:
n ≥ 3
सभी i+2 ≤ n के लिए Xᵢ + Xᵢ₊₁ = Xᵢ₊₂
अब मान लीजिए सख्ती से बढ़ते धनात्मक पूर्णांकों का एक ऐरे A एक अनुक्रम बनाता है, हमें A के सबसे लंबे फाइबोनैचि-जैसे उपअनुक्रम की लंबाई खोजनी है। यदि कोई मौजूद नहीं है, तो 0 लौटाएं।
उदाहरण के लिए, यदि संख्या [1,2,3,4,5,6,7,8] जैसी है, तो आउटपुट 5 होगा। सबसे लंबा उपअनुक्रम जो फाइबोनैचि है वह [1,2,3,5,8] जैसा है।
समाधान दृष्टिकोण
ret := 0, मैप m, n := A का आकार
dp मैट्रिक्स n×n बनाएं
i को 0 से n-1: m[A[i]] = i
j को i-1 से 0 तक: req = A[i] - A[j]
यदि req < A[j] और m में req है: dp[i][j] = max(dp[i][j], dp[j][m[req]]+1)
अन्यथा dp[i][j] = max(dp[i][j], 2)
ret अपडेट करें, अंत में ret ≥ 3 ? ret : 0 लौटाएं
C++ कार्यान्वयन
#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;
}
};
int main(){
vector<int> v = {1,2,3,4,5,6,7,8};
Solution ob;
cout << (ob.lenLongestFibSubseq(v));
return 0;
}
इनपुट
[1,2,3,4,5,6,7,8]
आउटपुट
5
