Length of Longest Fibonacci Subsequence
A sequence x1, x2, ..., xn is Fibonacci-like if:
n >= 3xi + xi+1 == xi+2for alli + 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.
Example 1
Input
arr = [1,2,3,4,5,6,7,8]Output
5The longest subsequence that is Fibonacci-like is [1, 2, 3, 5, 8].
Example 2
Input
arr = [1,3,7,11,12,14,18]Output
3The longest Fibonacci-like subsequences have length 3, such as [1, 11, 12], [3, 11, 14], or [7, 11, 18].
Constraints
- 3 <= arr.length <= 1000
- 1 <= arr[i] < arr[i + 1] <= 10^9