Medium

Length of Longest Fibonacci Subsequence

LAB

Given a strictly increasing array, return the length of the longest Fibonacci-like subsequence, or 0 if none has length at least 3.

EXAMPLES

Example 1

Input
{
  "arr": [
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8
  ]
}

Output
5

FUNCTION SHAPE

arr: intArray→int

SOLUTION NOTE

dp(i, j) = length of Fibonacci sequence ending at indices i, j. Previous element must be arr[j] - arr[i].

Reveal reference solution +

pythonREFERENCE

def lenLongestFibSubseq(self, arr: List[int]) -> int:
    index = {x: i for i, x in enumerate(arr)}
    n = len(arr)

    @cache
    def dp(i, j):
        # Length of fib sequence ending with arr[i], arr[j]
        target = arr[j] - arr[i]
        if target < arr[i] and target in index:
            return dp(index[target], i) + 1
        return 2

    res = 0
    for j in range(n):
        for i in range(j):
            res = max(res, dp(i, j))

    return res if res >= 3 else 0

TimeO(n²)

SpaceO(n²)

Open on LeetCode ↗