<p>A sequence <code>x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub></code> is <em>Fibonacci-like</em> if:</p>

<ul>
	<li><code>n &gt;= 3</code></li>
	<li><code>x<sub>i</sub> + x<sub>i+1</sub> == x<sub>i+2</sub></code> for all <code>i + 2 &lt;= n</code></li>
</ul>

<p>Given a <b>strictly increasing</b> array <code>arr</code> of positive integers forming a sequence, return <em>the <strong>length</strong> of the longest Fibonacci-like subsequence of</em> <code>arr</code>. If one does not exist, return <code>0</code>.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= arr.length &lt;= 1000</code></li>
	<li><code>1 &lt;= arr[i] &lt; arr[i + 1] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
public:

    int dp[1001][1002];
    unordered_map<int,int> m;

    int count(int s1,int s2){
        int cnt=2;

        while(m.find(s1+s2)!=m.end()){
            cnt++;
            int s=s1+s2;
            s1=s2;
            s2=s;
        }

        return cnt;
    }

    int helper(int i,int prev,vector<int>& arr){
        if(i>=arr.size()) return 0;
        if(dp[i][prev+1]!=-1) return dp[i][prev+1];

        int maxi=helper(i+1,prev,arr);

        if(prev==-1){
            return dp[i][prev+1]=max(1+helper(i+1,i,arr),helper(i+1,prev,arr));
        }

        int sum=arr[prev]+arr[i];

        if(m.find(sum)==m.end()) return 0;
        int idx=m[sum];

        return dp[i][prev+1]=1+helper(idx+1,idx,arr);
    }

    int lenLongestFibSubseq(vector<int>& arr) {
        int n=arr.size();
        int maxi=0;

        for(int i=0;i<n;i++) m[arr[i]]=i;

        // memset(dp,-1,sizeof(dp));

        // return 1+helper(0,-1,arr);

        
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                maxi=max(maxi,count(arr[i],arr[j]));
            }
        }

        if(maxi<3) maxi=0;

        return maxi;

    }
};
20200