<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 lenLongestFibSubseq(vector<int>& arr) {
/*int print0(vector<int> &b,int c,int e,int temp0){
    if(c==b.size()){
        return 0;
    }
    int temp2=0;
    if(e==-1){
        temp2=max(print0(b,c+1,c,temp0)+1,print0(b,c+1,e,temp0));
    }
    else if(temp0==-1){
        temp2=max(print0(b,c+1,e,c)+1,print0(b,c+1,e,temp0));
    }
    else if(e!=-1 && temp0!=-1){
        if(b[e]+b[temp0]==b[c]){
            temp2=print0(b,c+1,temp0,c)+1;
        }
        else if(b[e]+b[temp0]!=b[c]){
            temp2=print0(b,c+1,e,temp0);
        }
    }
    return temp2;
}
int lenLongestFibSubseq(vector<int> b){
    int c=0;
    int e=0;
    int temp0=-1;
    int temp2=-1;
    c=print0(b,e,temp0,temp2);
    int temp18=0;
    if(c>=3){
        temp18=c;
    }
    return temp18;
    }*/
    /*int print0(vector<int> &b,vector<vector<vector<int>>> &c,int e,int temp0,int temp2){
    if(e==b.size()){
        return 0;
    }
    int temp12=0;
    if(temp0!=-1 && temp2!=-1){
        if(c[e][temp0][temp2]!=-1){
            return c[e][temp0][temp2];
        }
    }
    if(temp0==-1){
        temp12=max(print0(b,c,e+1,e,temp2)+1,print0(b,c,e+1,temp0,temp2));
    }
    else if(temp2==-1){
        temp12=max(print0(b,c,e+1,temp0,e)+1,print0(b,c,e+1,temp0,temp2));
    }
    else if(temp0!=-1 && temp2!=-1){
        if(b[temp0]+b[temp2]==b[e]){
            temp12=print0(b,c,e+1,temp2,e)+1;
        }
        else if(b[temp0]+b[temp2]!=b[e]){
            temp12=print0(b,c,e+1,temp0,temp2);
        }
    }
   if(temp0!=-1 && temp2!=-1){
    c[e][temp0][temp2]=temp12;
   }
   return temp12;
}
int lenLongestFibSubseq(vector<int> b){
    int c=0;
    int e=-1;
    int temp0=-1;
    int temp2=0;
    vector<vector<vector<int>>> temp12;
    for(int temp18=0;temp18<b.size();temp18++){
        vector<vector<int>> temp28;
        for(int temp48=0;temp48<b.size();temp48++){
            vector<int> temp78;
            for(int temp92=0;temp92<b.size();temp92++){
                temp78.push_back(-1);
            }
            temp28.push_back(temp78);
        }
        temp12.push_back(temp28);
    }
    int temp18=0;
    temp18=print0(b,temp12,c,e,temp0);
    int temp28=0;
    if(temp18>=3){
        temp28=temp18;
    }
    return temp28;
}*/
int lenLongestFibSubseq(vector<int> &b){
    unordered_map<int,pair<int,int>> c;
    //vector<vector<int>> e;
    int e[1001][1001];
    int temp18=0;
    for(int temp0=0;temp0<b.size();temp0++){
        //vector<int> temp2;
        for(int temp12=0;temp12<b.size();temp12++){
            //temp2.push_back(0);
            e[temp0][temp12]=0;
        }
        //e.push_back(temp2);
    }
    for(int temp0=0;temp0<b.size();temp0++){
        c[b[temp0]].first=1;
        c[b[temp0]].second=temp0;
        //c[b[temp0]]=temp0;
    }
    for(int temp0=b.size()-1;temp0>=0;temp0--){
        for(int temp2=temp0+1;temp2<b.size();temp2++){
            //if(c[b[temp0]+b[temp2]].first==1){
                //if(c[b[temp0]+b[temp2]]!=0){
                    if(c.find(b[temp0]+b[temp2])!=c.end()){
                //e[temp0][temp2]=1+e[temp2][c[b[temp0]+b[temp2]].second];
                //e[temp0][temp2]=1+e[temp2][c[b[temp0]+b[temp2]]];
                e[temp0][temp2]=1+e[temp2][c.find(b[temp0]+b[temp2])->second.second];
                temp18=max(temp18,e[temp0][temp2]);
            }
        }
    }
    if(temp18>0){
        temp18=temp18+2;
    }
    return temp18;
}
};
20900