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


	n &gt;= 3
	xi + xi+1 == xi+2 for all i + 2 &lt;= 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].

&nbsp;
Example 1:

Input: arr = [1,2,3,4,5,6,7,8]
Output: 5
Explanation: The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:

Input: arr = [1,3,7,11,12,14,18]
Output: 3
Explanation: The longest subsequence that is fibonacci-like: [1,11,12], [3,11,14] or [7,11,18].

&nbsp;
Constraints:


	3 &lt;= arr.length &lt;= 1000
	1 &lt;= arr[i] &lt; arr[i + 1] &lt;= 109


class Solution(object): #DP. Time Complexity: O(N^2), Space Complexity: O(NlogM), M = max(A)
    def lenLongestFibSubseq(self, A):
        index = {Ai: i for i, Ai in enumerate(A)}
        dp = collections.defaultdict(lambda: 2)
        ans = 0
        for k, Ak in enumerate(A): #Following IJK idiom here
            for j in range(k-1,0,-1):            
                i = index.get(Ak - A[j], None)
                if Ak - A[j] >= A[j]: break #Pruning for illegal Ai
                if i is not None and i < j:
                    cur_len = dp[j, k] = dp[i, j] + 1
                    ans = max(ans, cur_len)
        
        return ans # ans is either 0 or >=3 for SURE
class Solution {
    /*
    * dp[i][j] is the max length of fibbonacci series whose last two elements
    * are A[i] & A[j]
    * for any integer A[k] we need to find two number A[i] & A[j] such that
    * i < j < k and A[i] + A[j] == A[k], we can find such pairs in O(n) time
    * complexity.
    * if there exist i,j,k such that i < j < k and A[i] + A[j] == A[k] then
    * dp[k][j] = dp[i][j] + 1 (A[k], A[j] are last two elements of fibbonacc series)
    */
    public int lenLongestFibSubseq(int[] A) {
        int n = A.length;
        int[][] dp = new int[n][n];
        int result = 0;
        for (int k = 2; k < n; k++) {
            int i = 0, j = k-1;
            while(i < j) {
                int sum = A[i] + A[j] - A[k];
                if (sum < 0) {
                    i++;
                } else if (sum > 0) {
                    j--;
                } else {
                    // ith, jth kth element are fibbonaci sequence
                    dp[j][k] = dp[i][j] + 1; // since numbers are unique
                    result = Math.max(result, dp[j][k]);
                    i++;
                    j--;
                }
            }
        }
        return result + 2 >= 3? result + 2: 0;
    }
}
class Solution {
public:

    int help(int i,int j, unordered_map<int,int> &mp,vector<int> &nums , vector<vector<int>> &dp){

        if(dp[i][j]!=-1)
            return dp[i][j];

        int x=nums[i]+nums[j];

        if(mp.find(x)!=mp.end())
        {
            dp[i][j]=help(j,mp[x],mp,nums,dp);
           return 1+dp[i][j];
        }

        return 1;
    }

   int solve(int idx ,int n, unordered_map<int,int> &mp,vector<int> &nums , vector<vector<int>> &dp)
    {
        int maxi=INT_MIN;

        for(int i=idx;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {

                int x=nums[i]+nums[j];

                if(mp.find(x)!=mp.end())
                {
                 maxi=max(maxi,2+help(j,mp[x],mp,nums,dp));
                }
            }
        }
        return (maxi==INT_MIN?0:maxi);
    }
    int lenLongestFibSubseq(vector<int>& arr) {

        unordered_map<int,int> mp;
        int n=arr.size();
        vector<vector<int>> dp(n,vector<int> (n,-1));

        for(int i=0;i<arr.size();i++)
            mp[arr[i]]=i;

       return solve(0,n,mp,arr,dp);

    }
};
var lenLongestFibSubseq = function(arr) {
    let ans = 2;
    const set = new Set(arr);
    const len = arr.length
    for(let i = 0; i < len; i++) {
        for(let j = i + 1; j < len; j++) {
            let a = arr[i], b = arr[j], len = 2;
            while(set.has(a + b)) {
                len++;
                let temp = a + b;
                a = b;
                b = temp;
            }
            ans = Math.max(len, ans);
        }
    }
    return ans == 2 ? 0 : ans;
};
Length of Longest Fibonacci Subsequence