Length of Longest Fibonacci Subsequence

medium dynamic programming hash table array

Problem

A sequence is Fibonacci-like if it has length ≥ 3 and every element is the sum of the previous two. Given a strictly increasing array arr, return the length of the longest Fibonacci-like subsequence. If none exists, return 0.

Inputarr = [1,2,3,4,5,6,7,8]

Output5

[1,2,3,5,8] is Fibonacci-like and has length 5.

arr (strictly increasing, comma-separated)

def len_longest_fib_subseq(arr):
    pos = {x: i for i, x in enumerate(arr)}
    dp = {}
    best = 0
    for j in range(len(arr)):
        for i in range(j):
            k = pos.get(arr[j] - arr[i], -1)
            if 0 <= k < i:
                dp[i, j] = dp.get((k, i), 2) + 1
            else:
                dp[i, j] = 2
            best = max(best, dp[i, j])
    return best if best >= 3 else 0

function lenLongestFibSubseq(arr) {
  const pos = new Map(arr.map((x, i) => [x, i]));
  const dp = new Map();
  let best = 0;
  for (let j = 0; j < arr.length; j++) {
    for (let i = 0; i < j; i++) {
      const k = pos.has(arr[j] - arr[i]) ? pos.get(arr[j] - arr[i]) : -1;
      const len = (k >= 0 && k < i) ? (dp.get(k * arr.length + i) || 2) + 1 : 2;
      dp.set(i * arr.length + j, len);
      best = Math.max(best, len);
    }
  }
  return best >= 3 ? best : 0;
}

int lenLongestFibSubseq(int[] arr) {
    int n = arr.length;
    Map<Integer, Integer> pos = new HashMap<>();
    for (int i = 0; i < n; i++) pos.put(arr[i], i);
    int[][] dp = new int[n][n];
    int best = 0;
    for (int j = 0; j < n; j++)
        for (int i = 0; i < j; i++) {
            Integer k = pos.get(arr[j] - arr[i]);
            dp[i][j] = (k != null && k < i) ? Math.max(dp[k][i], 2) + 1 : 2;
            best = Math.max(best, dp[i][j]);
        }
    return best >= 3 ? best : 0;
}

int lenLongestFibSubseq(vector<int>& arr) {
    int n = arr.size(), best = 0;
    unordered_map<int,int> pos;
    for (int i = 0; i < n; i++) pos[arr[i]] = i;
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int j = 0; j < n; j++)
        for (int i = 0; i < j; i++) {
            auto it = pos.find(arr[j] - arr[i]);
            int k = (it != pos.end()) ? it->second : -1;
            dp[i][j] = (k >= 0 && k < i) ? max(dp[k][i], 2) + 1 : 2;
            best = max(best, dp[i][j]);
        }
    return best >= 3 ? best : 0;
}

Explanation

A Fibonacci-like sequence is one where each number is the sum of the previous two. Here's the key realization: any two chosen elements completely determine the rest of the chain, because the next value is forced to be their sum.

So we run a DP over pairs of indices. We use dp[i, j] = the length of the longest Fibonacci-like chain whose last two elements sit at positions i and j.

For a pair (i, j), the element that should come before them has value arr[j] - arr[i]. We look it up in pos (a value-to-index map). If it exists at some earlier index k < i, we extend that chain: dp[i,j] = dp[k,i] + 1. Otherwise the pair just starts a fresh chain of length 2.

We track the largest length seen, and return it only if it is at least 3 (a real Fibonacci-like sequence needs three elements).

Example: arr = [1,2,3,4,5,6,7,8]. The chain [1,2,3,5,8] builds up pair by pair to length 5, which is the answer.

Time: O(n²) Space: O(n²)