Fork me on GitHub

Length of Longest Fibonacci Subsequence

Posted on

Description

https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        int size = A.size();
        unordered_map<int, int> counter;
        for (int i = 0; i < size; ++i) counter[A[i]] = i;
        
        vector<vector<int>> dp(size, vector<int>(size, 2));
        
        int ret = 0;
        for (int i = 1; i < size - 1; ++i) {
            for (int j = i + 1; j < size; ++j){
                int target = A[j] - A[i];
                if (target >= A[i]) break;
                auto iter = counter.find(target);
                if (iter == counter.end()) continue;
                dp[i][j] = dp[iter->second][i] + 1;
                ret = max(ret, dp[i][j]);
            }
        }
        return ret;
    }
};