# LeetCode 873: Length of Longest Fibonacci Subsequence

## Problem Restatement

We are given a strictly increasing array `arr` of positive integers.

We need to return the length of the longest Fibonacci-like subsequence.

A sequence is Fibonacci-like if:

1. Its length is at least `3`.
2. For every valid position:

```python
x[i] + x[i + 1] == x[i + 2]
```

A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements.

If no Fibonacci-like subsequence exists, return `0`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `arr`, a strictly increasing array of positive integers |
| Output | Length of the longest Fibonacci-like subsequence |
| Failure case | Return `0` if no valid sequence of length at least `3` exists |
| Constraint | `3 <= arr.length <= 1000` |

Function shape:

```python
class Solution:
    def lenLongestFibSubseq(self, arr: list[int]) -> int:
        ...
```

## Examples

Example 1:

```python
arr = [1, 2, 3, 4, 5, 6, 7, 8]
```

One longest Fibonacci-like subsequence is:

```python
[1, 2, 3, 5, 8]
```

It has length:

```python
5
```

So the answer is:

```python
5
```

Example 2:

```python
arr = [1, 3, 7, 11, 12, 14, 18]
```

Some Fibonacci-like subsequences are:

```python
[1, 11, 12]
[3, 11, 14]
[7, 11, 18]
```

The longest length is `3`.

So the answer is:

```python
3
```

## First Thought: Try Every Starting Pair

Once we choose the first two numbers of a Fibonacci-like sequence, the rest is determined.

For example, if the first two numbers are:

```python
1, 2
```

then the next values must be:

```python
3, 5, 8, 13, ...
```

So one direct method is:

1. Try every pair `(arr[i], arr[j])`.
2. Keep adding the next required value.
3. Use a set to check whether that value exists.
4. Track the longest length.

This works, but trying every pair and extending greedily can still do repeated work.

A dynamic programming solution records the best length for each ending pair.

## Key Insight

A Fibonacci-like sequence is determined by its last two values.

Suppose a sequence ends with:

```python
arr[j], arr[k]
```

Then the previous value must be:

```python
arr[k] - arr[j]
```

So if there is an index `i` such that:

```python
arr[i] + arr[j] == arr[k]
```

then we can extend the sequence ending with `(arr[i], arr[j])` by adding `arr[k]`.

Define:

```python
dp[j][k]
```

as the length of the longest Fibonacci-like subsequence ending with:

```python
arr[j], arr[k]
```

Then:

```python
dp[j][k] = dp[i][j] + 1
```

when:

```python
arr[i] = arr[k] - arr[j]
```

and:

```python
i < j
```

We use a hash map from value to index to find `i` quickly.

## Algorithm

Create a dictionary:

```python
index = {value: position}
```

Initialize a 2D DP table with `2`, because any pair can be the start of a possible Fibonacci-like sequence:

```python
dp = [[2] * n for _ in range(n)]
```

Then iterate over all pairs `(j, k)` with `j < k`.

For each pair:

1. Compute:

```python
prev = arr[k] - arr[j]
```

2. Check whether `prev` exists in the array.
3. Its index must be less than `j`.
4. If valid, update:

```python
dp[j][k] = dp[i][j] + 1
```

5. Update the answer.

At the end, return the answer if it is at least `3`. Otherwise return `0`.

## Correctness

For every pair `(j, k)`, `dp[j][k]` represents the longest Fibonacci-like subsequence ending with `arr[j]` and `arr[k]`.

The base length is `2`, because any two numbers can be treated as a candidate pair before a third number is added.

If a valid previous value exists, then any Fibonacci-like subsequence ending with `arr[i]` and `arr[j]` can be extended by `arr[k]`, because:

```python
arr[i] + arr[j] == arr[k]
```

So `dp[i][j] + 1` is a valid length for a sequence ending at `(j, k)`.

Because `arr` is strictly increasing, the value-to-index map gives at most one possible previous index. The condition `i < j` preserves subsequence order.

The algorithm considers every possible ending pair `(j, k)`, so every Fibonacci-like subsequence is considered at the moment its last two elements are processed.

Therefore, the maximum value found is the length of the longest Fibonacci-like subsequence. If the maximum never reaches `3`, no valid Fibonacci-like subsequence exists, so returning `0` is correct.

## Complexity

Let:

```python
n = len(arr)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | We process every pair `(j, k)` once |
| Space | `O(n^2)` | The DP table stores one value per pair |

The hash map gives `O(1)` expected lookup time.

## Implementation

```python
class Solution:
    def lenLongestFibSubseq(self, arr: list[int]) -> int:
        n = len(arr)
        index = {value: i for i, value in enumerate(arr)}

        dp = [[2] * n for _ in range(n)]
        answer = 0

        for k in range(n):
            for j in range(k):
                prev = arr[k] - arr[j]

                if prev >= arr[j]:
                    continue

                if prev not in index:
                    continue

                i = index[prev]
                dp[j][k] = dp[i][j] + 1
                answer = max(answer, dp[j][k])

        return answer if answer >= 3 else 0
```

## Code Explanation

We first build the index map:

```python
index = {value: i for i, value in enumerate(arr)}
```

This lets us quickly find whether a needed previous value exists.

The DP table starts with length `2` for every pair:

```python
dp = [[2] * n for _ in range(n)]
```

Then we choose the last index `k` and the second-last index `j`:

```python
for k in range(n):
    for j in range(k):
```

The previous value must be:

```python
prev = arr[k] - arr[j]
```

Since the array is strictly increasing and we need `i < j`, the previous value must be smaller than `arr[j]`:

```python
if prev >= arr[j]:
    continue
```

If `prev` does not appear in the array:

```python
if prev not in index:
    continue
```

then no valid previous element exists.

Otherwise, we extend the sequence:

```python
i = index[prev]
dp[j][k] = dp[i][j] + 1
```

and update the best answer:

```python
answer = max(answer, dp[j][k])
```

Finally:

```python
return answer if answer >= 3 else 0
```

returns `0` when no Fibonacci-like subsequence exists.

## Testing

```python
def test_len_longest_fib_subseq():
    s = Solution()

    assert s.lenLongestFibSubseq([1, 2, 3, 4, 5, 6, 7, 8]) == 5

    assert s.lenLongestFibSubseq([1, 3, 7, 11, 12, 14, 18]) == 3

    assert s.lenLongestFibSubseq([1, 4, 10, 20]) == 0

    assert s.lenLongestFibSubseq([1, 2, 3]) == 3

    assert s.lenLongestFibSubseq([2, 4, 6, 10, 16, 26]) == 6

    print("all tests passed")

test_len_longest_fib_subseq()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 2, 3, 4, 5, 6, 7, 8]` | Standard long sequence |
| `[1, 3, 7, 11, 12, 14, 18]` | Only length-3 sequences |
| `[1, 4, 10, 20]` | No valid Fibonacci-like subsequence |
| `[1, 2, 3]` | Minimum valid length |
| `[2, 4, 6, 10, 16, 26]` | Entire array is Fibonacci-like |