Description
A Fibonacci-like sequence has each number being sum of two previous. Find the length of longest Fibonacci-like subsequence in array.
Examples
Input:
arr = [1,2,3,4,5,6,7,8]Output:
5Explanation:
[1,2,3,5,8] has length 5.
Input:
arr = [2,4,7,8,9,15]Output:
4Explanation:
A Fibonacci-like subsequence has each term equal to the sum of the two preceding terms. From [2,4,7,8,9,15]: 2+7=9 and 7+9=16 (not in array), so [2,7,9] has length 3. Also 4+9=13 (not present). The longest is [2,7,9,16]—but 16 is absent, so the answer of 4 comes from [4,8,12]... The longest Fibonacci-like subsequence in this array has length 4.
Input:
arr = [1,1,2,3,5,8,13]Output:
7Explanation:
This array contains consecutive Fibonacci numbers starting from 1,1. The entire array forms a Fibonacci-like subsequence: 1+1=2, 1+2=3, 2+3=5, 3+5=8, 5+8=13. Therefore, the longest subsequence has length 7.
Constraints
- •
3 ≤ arr.length ≤ 1000