<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) {
        const int n = arr.size();
        const auto BinSearch = [&](int val) -> int {
            int left = 0;
            int right = n - 1;

            while (left <= right) {
                int mid = left + (right - left + 1) / 2;
                if (arr[mid] == val)
                    return mid;

                if (arr[mid] < val)
                    left = mid + 1;
                else
                    right = mid - 1;
            }

            return -1;
        };

        vector<vector<int>> DpMatrix(n, vector<int>(n, 0));

        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                int nextVal = arr[i] + arr[j];

                if (nextVal > *(arr.end() - 1))
                    break;

                int nextIndex = BinSearch(nextVal);

                if (nextIndex != -1){
                    if (DpMatrix[i][nextIndex] == 0)
                        DpMatrix[j][i] = 3;
                    else
                        DpMatrix[j][i] = DpMatrix[i][nextIndex] + 1;
                }
            }
        }

        int maxLen = 0;
        for (auto &i : DpMatrix)
            maxLen = max(maxLen, *max_element(i.begin(), i.end()));

        return maxLen;     
    }

private:
    void PrintMatrix(vector<vector<int>> &Matrix) const {
        for (auto &i : Matrix){
            for (int j : i)
                cout << j << " ";
            cout << endl;
        }
    }
};
146300