LeetCode 873. LeetCode 873. Length of Longest Fibonacci Subsequence
原题链接
简单
作者:
haaai
,
2021-01-08 14:04:49
,
所有人可见
,
阅读 417
class Solution {
public:
unordered_map<int, int> dict;
int lenLongestFibSubseq(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i<n; i++)
dict[arr[i]] = i;
vector<vector<int>> dp(n+1, vector<int> (n+1, 0));
int ans = 0;
for (int i = 1; i<n; i++)
for (int j = i-1; j>=0; j--){
dp[j][i] = 2;
int x = arr[i] - arr[j];
if (!dict.count(x)) continue;
dp[j][i] = max(dp[j][i], dp[dict[x]][j] + 1);
ans = max(ans, dp[j][i]);
}
return ans > 2? ans : 0;
}
};