873. Length of Longest Fibonacci Subsequence

A sequence x1, x2, …, xn is Fibonacci-like if:

• n >= 3
• xi + xi+1 == xi+2 for all i + 2 <= n

Given a strictly increasing array arr of positive integers forming a sequence, return the length of the longest Fibonacci-like subsequence of arr. If one does not exist, return 0.

A subsequence is derived from another sequence arr by deleting any number of elements (including none) from arr, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].

class Solution {
    unordered_map<int, int> mp;
    int dp[1010][1010];
    int helper(vector<int>& A, int i, int j) {
        if(dp[i][j] != -1) return dp[i][j];
        dp[i][j] = 2;
        
        if(mp.count(A[i] + A[j]))
            dp[i][j] = 1 + helper(A, j, mp[A[i] + A[j]]);
        
        return dp[i][j];
    }
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        for(int i = 0; i < arr.size(); i++) mp[arr[i]] = i;
        memset(dp, -1, sizeof dp);
        int res = 0;
        
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i + 1; j < n; j++) {
                res = max(res, helper(arr, i, j));
            }
        }
        
        return res > 2 ? res : 0;
    }
};