Length of Longest Fibonacci Subsequence

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:

• we can initialize left and right indices at 0 and i-1 respectively
• then,
  • if arr[left] + arr[right] < arr[i], we increment left to increase arr[left] + arr[right]
  • if arr[left] + arr[right] > arr[i], we decrement right to decrease arr[left] + arr[right]
  • if arr[left] + arr[right] == arr[i], we check for the value inside dp[right][left] and make dp[i][right] = dp[right][left] + 1
• we repeat the above steps until left >= right, which is when we iterate to the next index i+1

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

• Time: O(n^2)
• Space: O(n^2)