<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][1001];
    int find(int i,int prev,int& n,vector<int>& arr,unordered_map<int,int>& mp){
        if(i >= n) return 0;
        if(dp[i][prev+1]!=-1)
        return dp[i][prev+1];
        int pick = 0,dont = 0;
        if(prev == -1){
            dont = find(i+1,prev,n,arr,mp);
            for(int j = i+1;j<n-1;j++){
                pick = max(pick,find(j,i,n,arr,mp));
            }
        }else{
            int x = arr[prev], y = arr[i];
            if(mp.find(x+y)!=mp.end()){
                pick = 1 + find(mp[x+y],i,n,arr,mp);
            }
        }
        return  dp[i][prev+1] = max(dont,pick);
    }
    int lenLongestFibSubseq(vector<int>& arr) {
        unordered_map<int,int>mp;
        int n = arr.size();
        memset(dp,-1,sizeof dp);
        for(int i=0;i<n;i++) mp[arr[i]] = i;
        int x = find(0,-1,n,arr,mp);
        return (x > 0) ? 2 + x : 0;
    }
};
// class Solution {
// public:
//     int dp[1001][1001];
//     vector<vector<int>> subsequences;  // Store all subsequences considered

//     int find(int i, int prev, int& n, vector<int>& arr, unordered_map<int, int>& mp, vector<int> currentSubseq) {
//         if (i >= n){
//             subsequences.push_back(currentSubseq);  // Save the subsequence
//             return 0; 
//         }  // Base case: reached the end of the array
//         // if (dp[i][prev + 1] != -1) return dp[i][prev + 1];  // Use memoized value

//         int pick = 0, dont = 0;

//         if (prev == -1) {
//             // If prev is -1, we are free to pick or not pick the current element
//             currentSubseq.push_back(arr[i]);
//             pick = find(i + 1, i, n, arr, mp, currentSubseq);  // Pick the current element
//             currentSubseq.pop_back();  // Undo the change for the "don't pick" case
//             dont = find(i + 1, prev, n, arr, mp, currentSubseq);  // Don't pick the current element
//         } else {
//             int x = arr[prev], y = arr[i];
            
//             // Check if the next Fibonacci number exists in the array
//             if (mp.find(x + y) != mp.end()) {
//                 currentSubseq.push_back(y);  // Add current element to the subsequence
//                 pick = 1 + find(mp[x + y], i, n, arr, mp, currentSubseq);  // Continue the sequence
//                 // subsequences.push_back(currentSubseq);  // Save the subsequence
//                 currentSubseq.pop_back();  // Backtrack
//             }else
//             dont = find(i + 1, prev, n, arr, mp, currentSubseq);  // Skip the current element
//         }

//         return dp[i][prev + 1] = max(dont, pick);
//     }

//     int lenLongestFibSubseq(vector<int>& arr) {
//         unordered_map<int, int> mp;
//         int n = arr.size();
//         memset(dp, -1, sizeof dp);  // Initialize dp array with -1

//         // Create a map to store the index of each element
//         for (int i = 0; i < n; i++) {
//             mp[arr[i]] = i;
//         }

//         vector<int> currentSubseq;  // Temporary vector to store current subsequence
//         int x = find(0, -1, n, arr, mp, currentSubseq);
//         cout << "Maximum length of Fibonacci-like subsequence found: " << x << endl;
        
//         // Print all subsequences considered
//         cout << "Subsequences considered:\n";
//         for (auto& subseq : subsequences) {
//             for (int num : subseq) {
//                 cout << num << " ";
//             }
//             cout << endl;
//         }
//         if(mp.find(2+4)!=mp.end()){
//             cout<<"yes "<<mp[6]<<endl;
//         }
//         // If x is greater than 0, return the length (2 + subsequence), otherwise 0
//         return (x > 0) ? 2 + x : 0;
//     }
// };

20600