#873

Length of Longest Fibonacci Subsequence

specialist · 750 · lc medium +31 · verified · 57.5% accepted · 2,694 likes · top 53%

Description

A sequence x1, x2, ..., xn is Fibonacci-like if:

- n >= 3

- xi + xi+1 == xi+2 for all valid i

Given a strictly increasing array arr of positive integers, return the length of its longest Fibonacci-like subsequence. Return 0 if no such subsequence of length at least 3 exists.

A subsequence is obtained by deleting some (possibly zero) elements 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].

Code

1

2

3

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int: