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

# Length of Longest Fibonacci Subsequence

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`
* *(The time limit has been reduced by 50% for submissions in Java, C, and C++.)*

```java
class Solution {
    public int lenLongestFibSubseq(int[] A) {
        int dp[][] = new int[A.length][A.length], max = 0;
        // dp[i][j] is the length of longest fibnacci subsequence length
        // which has A[i] as 2nd last and A[j] as last numbers in sequence
        for (int i = 2; i < A.length; i++) {
            // Given strictly increasing array
            int start = 0, end = i - 1;
            while (start < end) {
                int sum = A[start] + A[end];
                if (sum > A[i])
                    end--;
                else if (sum < A[i])
                    start++;
                else {
                    // If we are starting a new sequence then we need to add 2
                    // because dp[start][end] will be 0 at this point
                    dp[end][i] = 1 + (dp[start][end] == 0 ? 2 : dp[start][end]);
                    max = Math.max(max, dp[end][i]);
                    start++;
                    end--;
                }
            }
        }
        return max;
    }
}
```