> For the complete documentation index, see [llms.txt](https://twchen.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://twchen.gitbook.io/leetcode/array/length-of-longest-fibonacci-subsequence.md).

# Length of Longest Fibonacci Subsequence

## Description

A sequence `X_1, X_2, ..., X_n` is *fibonacci-like* if:

* `n >= 3`
* `X_i + X_{i+1} = X_{i+2}` for all `i + 2 <= n`

Given a **strictly increasing** array `A` of positive integers forming a sequence, find the **length** of the longest fibonacci-like subsequence of `A`.  If one does not exist, return 0.

(*Recall that a subsequence is derived from another sequence `A` by deleting any number of elements (including none) from `A`, without changing the order of the remaining elements.  For example, `[3, 5, 8]` is a subsequence of `[3, 4, 5, 6, 7, 8]`.*)

**Example 1:**

```
Input: [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: [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].
```

**Note:**

* `3 <= A.length <= 1000`
* `1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9`

## Solution

Both the time complexity and the space complexity are $$O(n^2)$$.

```cpp
class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        int n = A.size();
        // dp[j][i]: length of the longest Fibonacci sequence ending with (A[j], A[i]).
        vector<vector<int>> dp(n, vector<int>(n));
        unordered_map<int, int> num2idx;
        for(int i = 0; i < n; ++i){
            num2idx[A[i]] = i;
        }
        int len = 0;
        for(int i = 1; i < A.size(); ++i){
            for(int j = 0; j < i; ++j){
                int a = A[i] - A[j];
                int b = A[j];
                int c = A[i];
                // check whether there is a k such that
                // k < j < i and (A[k], A[j], A[i]) is fibonacci-like
                if(a >= b){
                    // not possible to find A[k] because A[k] < A[j]
                    dp[j][i] = 2;
                }else{
                    auto it = num2idx.find(a);
                    if(it != num2idx.end()){
                        dp[j][i] = dp[it->second][j] + 1;
                        len = max(len, dp[j][i]);
                    }else{
                        dp[j][i] = 2;
                    }
                }
            }
        }
        return len;
    }
};
```