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:
3Explanation:
A Fibonacci-like subsequence has each term equal to the sum of the two preceding terms. In [2,4,7,8,9,15], the longest valid subsequence is [2,7,9], which has length 3.
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