# Length of Longest Fibonacci Subsequence
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/length-of-longest-fibonacci-subsequence)
Canonical: https://scaleengineer.com/dsa/problems/length-of-longest-fibonacci-subsequence
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Hash Table
**Companies:** [Baidu](https://scaleengineer.com/companies/baidu)
---
## Problem
A sequence `x1, x2, ..., xn` is _Fibonacci-like_ if:

* `n >= 3`
* `xi + xi+1 == xi+2` for all `i + 2 <= n`

Given a **strictly increasing** array `arr` of positive integers forming a sequence, return _the **length** of the longest Fibonacci-like subsequence of_ `arr`. If one does not exist, return `0`.

A **subsequence** is derived from another sequence `arr` by deleting any number of elements (including none) from `arr`, 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:** arr = [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:** 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] <= 109`

# Approaches
## Brute Force with Set
This approach involves checking every possible pair of elements from the array to see if they can be the first two elements of a Fibonacci-like subsequence. For each starting pair, we then greedily extend the subsequence as long as possible.
**Time:** O(N^2 * log(M)), where N is the number of elements in `arr` and M is the maximum value in `arr`. The O(N^2) comes from the nested loops to pick pairs. The `log(M)` factor comes from the `while` loop, as the values in a Fibonacci-like sequence grow exponentially, so the number of terms until they exceed M is proportional to `log(M)`. · **Space:** O(N) to store the elements in the `HashSet`.
**Pros:** Relatively simple to understand and implement.; Space efficient compared to the DP approach.
**Cons:** The time complexity is worse than the dynamic programming approach, which can be significant for larger N.; It re-computes the length of the same sub-problems multiple times. For example, the length of the sequence ending in (3, 5) might be calculated when starting with (1, 2) and also when starting with (2, 3).
### Explanation
The core idea is that a Fibonacci-like sequence is determined by its first two elements. If we pick `arr[i]` and `arr[j]` as the first two terms, the third term must be `arr[i] + arr[j]`, the fourth must be `arr[j] + (arr[i] + arr[j])`, and so on.

To efficiently check if the next required number exists in the input array, we first store all elements of `arr` into a `HashSet`. This provides average O(1) time complexity for lookups.

We then iterate through all possible pairs `(arr[i], arr[j])` with `i < j`. For each pair, we start a potential Fibonacci-like subsequence of length 2.

We then repeatedly calculate the next expected term and check if it's in our hash set. If it is, we increment our current subsequence length and continue with the next two terms.

We keep track of the maximum length found across all starting pairs. If the longest sequence found has a length less than 3, we return 0 as per the problem description.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        if (n < 3) {
            return 0;
        }

        Set<Integer> numSet = new HashSet<>();
        for (int x : arr) {
            numSet.add(x);
        }

        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int a = arr[i];
                int b = arr[j];
                int currentLength = 2;
                
                while (numSet.contains(a + b)) {
                    int next = a + b;
                    a = b;
                    b = next;
                    currentLength++;
                }
                
                if (currentLength > 2) {
                    maxLength = Math.max(maxLength, currentLength);
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Get the length of the array, `n`. If `n < 3`, return 0.
- Create a `HashSet` called `numSet` and add all elements from `arr` to it for O(1) average time lookups.
- Initialize a variable `maxLength` to 0.
- Iterate through the array with an outer loop for index `i` from 0 to `n-1`.
- Iterate with an inner loop for index `j` from `i+1` to `n-1`.
- Inside the inner loop, let `a = arr[i]` and `b = arr[j]`. Initialize `currentLength = 2`.
- Start a `while` loop to extend the sequence. The condition is `numSet.contains(a + b)`.
- Inside the `while` loop:
    - Calculate `next = a + b`.
    - Increment `currentLength`.
    - Update `a` to `b` and `b` to `next` for the next iteration.
- After the `while` loop, if `currentLength > 2`, update `maxLength = max(maxLength, currentLength)`.
- After the loops complete, return `maxLength`.

## Dynamic Programming
This approach uses dynamic programming to avoid re-computation. We build a 2D DP table to store the lengths of Fibonacci-like subsequences ending at specific pairs of elements.
**Time:** O(N^2). The nested loops iterate through approximately N^2/2 pairs of `(j, k)`. The operations inside the loop (map lookup, arithmetic) are O(1) on average. · **Space:** O(N^2). We use an O(N^2) DP table to store the intermediate results and an O(N) map for value-to-index lookups. The dominant factor is the DP table.
**Pros:** More time-efficient than the brute-force approach.; Avoids redundant calculations by storing results in the DP table.
**Cons:** Requires O(N^2) space, which could be an issue for very large N (though N <= 1000 is acceptable in this problem).
### Explanation
Let `dp[j][k]` be the length of the longest Fibonacci-like subsequence that ends with `arr[j]` and `arr[k]`, where `j < k`.

The base case for any pair `(arr[j], arr[k])` is a length of 2.

To compute `dp[j][k]`, we need to find the previous element in the sequence. Let this element be `arr[i]`. The relationship must be `arr[i] + arr[j] = arr[k]`. This means `arr[i] = arr[k] - arr[j]`.

We can find `arr[i]` efficiently if we first store the array's values and their indices in a `HashMap`.

If we find an index `i` such that `arr[i] = arr[k] - arr[j]` and `i < j`, it means we can extend the subsequence ending at `(arr[i], arr[j])`. The new length will be `dp[i][j] + 1`.

So, the transition is: `dp[j][k] = dp[i][j] + 1`. If no such `i` exists, `dp[j][k]` represents a sequence of just two elements, so its length is 2.

We iterate through all possible ending pairs `(arr[j], arr[k])` and fill the `dp` table. The maximum value found in the `dp` table will be our answer. If the maximum length is 2, it means no Fibonacci-like subsequence of length 3 or more exists, so we return 0.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        if (n < 3) {
            return 0;
        }

        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            indexMap.put(arr[i], i);
        }

        int[][] dp = new int[n][n];
        int maxLength = 0;

        for (int k = 1; k < n; k++) {
            for (int j = 0; j < k; j++) {
                int target = arr[k] - arr[j];
                // We need target < arr[j] because arr is strictly increasing.
                // If target >= arr[j], then its index i would be >= j.
                if (target < arr[j] && indexMap.containsKey(target)) {
                    int i = indexMap.get(target);
                    // The length of sequence ending at j, k is one more than
                    // the length of sequence ending at i, j.
                    dp[j][k] = dp[i][j] + 1;
                } else {
                    // This is the base case, a sequence of length 2.
                    dp[j][k] = 2;
                }
                maxLength = Math.max(maxLength, dp[j][k]);
            }
        }

        return maxLength > 2 ? maxLength : 0;
    }
}
```
### Algorithm
- Get the length of the array, `n`. If `n < 3`, return 0.
- Create a `HashMap` `indexMap` to store each number and its index in `arr`.
- Initialize a 2D array `dp[n][n]` to store the lengths.
- Initialize a variable `maxLength` to 0.
- Iterate `k` from 1 to `n-1`.
- Iterate `j` from 0 to `k-1`.
- Calculate `target = arr[k] - arr[j]`.
- Check if `target` exists in `indexMap` and if `target` is less than `arr[j]`. The second condition ensures that the index `i` of `target` will be less than `j` because the array is strictly increasing.
- If the condition is met:
    - Get the index `i = indexMap.get(target)`.
    - Set `dp[j][k] = dp[i][j] + 1`.
- Else:
    - Set `dp[j][k] = 2`.
- Update `maxLength = max(maxLength, dp[j][k])`.
- After the loops, if `maxLength` is greater than 2, return `maxLength`. Otherwise, return 0.

# Solutions
### Java

```java
class Solution {
public
  int lenLongestFibSubseq(int[] arr) {
    int n = arr.length;
    Map<Integer, Integer> mp = new HashMap<>();
    for (int i = 0; i < n; ++i) {
      mp.put(arr[i], i);
    }
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        dp[j][i] = 2;
      }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        int d = arr[i] - arr[j];
        if (mp.containsKey(d)) {
          int k = mp.get(d);
          if (k < j) {
            dp[j][i] = Math.max(dp[j][i], dp[k][j] + 1);
            ans = Math.max(ans, dp[j][i]);
          }
        }
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} arr * @return {number} */ var lenLongestFibSubseq =
  function (arr) {
    const mp = new Map();
    const n = arr.length;
    const dp = new Array(n).fill(0).map(() => new Array(n).fill(0));
    for (let i = 0; i < n; ++i) {
      mp.set(arr[i], i);
      for (let j = 0; j < i; ++j) {
        dp[j][i] = 2;
      }
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
      for (let j = 0; j < i; ++j) {
        const d = arr[i] - arr[j];
        if (mp.has(d)) {
          const k = mp.get(d);
          if (k < j) {
            dp[j][i] = Math.max(dp[j][i], dp[k][j] + 1);
            ans = Math.max(ans, dp[j][i]);
          }
        }
      }
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  int lenLongestFibSubseq(vector<int> &arr) {
    unordered_map<int, int> mp;
    int n = arr.size();
    for (int i = 0; i < n; ++i)
      mp[arr[i]] = i;
    vector<vector<int>> dp(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < i; ++j)
        dp[j][i] = 2;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        int d = arr[i] - arr[j];
        if (mp.count(d)) {
          int k = mp[d];
          if (k < j) {
            dp[j][i] = max(dp[j][i], dp[k][j] + 1);
            ans = max(ans, dp[j][i]);
          }
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int: mp = {v: i for i, v in enumerate(arr)} n = len(arr) dp = [[0] * n for _ in range(n)] for i in range(n): for j in range(i): dp[j][i] = 2 ans = 0 for i in range(n): for j in range(i): d = arr[i] - arr[j] if d in mp and (k: = mp[d]) < j: dp[j][i] = max(dp[j][i], dp[k][j] + 1) ans = max(ans, dp[j][i]) return ans

```