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

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: