Length of Longest Fibonacci Subsequence — LeetCode 873 Python Solution

The 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.

Example

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].

Python solution

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

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 873. Length of Longest Fibonacci Subsequence is filed here because LeetCode tags it Dynamic Programming, which is the vocabulary this hub collects.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems