> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Length of Longest Fibonacci Subsequence

> Tested Python solution for LeetCode 873 with 14 pytest cases. Generate a practice environment with lcpy.

LeetCode 873, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Hash Table](/catalog/topics/hash-table), [Dynamic Programming](/catalog/topics/dynamic-programming). [View on LeetCode](https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/description/).

Generate this problem as a practice environment: tested reference solution, 14 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 873   # by problem number
lcpy gen -s length_of_longest_fibonacci_subsequence   # by problem name
```

## Problem

A sequence \<code>x1, x2, ..., xn\</code> is \<em>Fibonacci-like\</em> if:\</p>

\<ul>
\<li>\<code>n >= 3\</code>\</li>
\<li>\<code>xi + xi+1 == xi+2\</code> for all \<code>i + 2 \<= n\</code>\</li>
\</ul>

\<p>Given a \<strong>strictly increasing\</strong> array \<code>arr\</code> of positive integers forming a sequence, return \<em>the length of the longest Fibonacci-like subsequence of\</em> \<code>arr\</code>. If one does not exist, return \<code>0\</code>.\</p>

\<p>A \<em>subsequence\</em> 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>.

### Examples

```
Input: arr = [1,2,3,4,5,6,7,8]
Output: 5
Explanation: The longest subsequence that is Fibonacci-like: [1,2,3,5,8].
```

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

### Constraints

* 3 \<= arr.length \<= 1000
* 1 \<= arr\[i] \< arr\[i + 1] \<= 10^9

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/length_of_longest_fibonacci_subsequence/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/length_of_longest_fibonacci_subsequence/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n^2)
    # Space: O(n^2)
    def len_longest_fib_subsequence(self, arr: list[int]) -> int:
        index = {num: i for i, num in enumerate(arr)}
        dp: dict[tuple[int, int], int] = {}
        best = 0
        for j in range(len(arr)):
            for i in range(j):
                need = arr[j] - arr[i]
                if need < arr[i] and need in index:
                    dp[(i, j)] = dp.get((index[need], i), 2) + 1
                    best = max(best, dp[(i, j)])
        return best
```

## Complexity

| Time | Space |
| - | - |
| O(n^2) | O(n^2) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.