873: Length-of-Longest-Fibonacci-Subsequence
Medium

table of contents

This problem might be screaming dynamic programming, due to its requirements to find the maximum length Fibonacci subsequence.

For this, we basically iterate through the array arr, and use a 2 pointers approach to finding pairs. If iterated to index i, 2 <= i <= arr.size(), then:

Finally, we just return the maximum element inside dp. If this element is equal to 2, then we return 0 (since there is no valid Fibonacci sequence)

code

class Solution {``
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        vector<vector<int>> dp (arr.size(), vector<int>(arr.size(), 2));

        int ans = 0;
        for (int i = 2; i < arr.size(); ++i) {
            int left = 0;
            int right = i-1;
            while (left < right) {
                if (arr[left] + arr[right] < arr[i]) {
                    ++left;
                } else if (arr[left] + arr[right] > arr[i]) {
                    --right;
                } else {
                    dp[i][right] = dp[right][left] + 1;
                    ans = max(dp[i][right], ans);
                    ++left;
                    --right;
                }
            }
        }
        return ans == 2 ? 0 : ans;
    }
};

complexity