mediumDynamic Programming 2DPure DSA~25 min
Longest Fibonacci-Like Subsequence
Analysts look for self-reinforcing growth in a strictly increasing metric series — where each value equals the sum of the two before it. Find the longest such Fibonacci-like subsequence.
Problem
Given a strictly increasing array arr of positive integers, return the length of the longest subsequence that is Fibonacci-like: it has length >= 3 and every element (from the third on) equals the sum of the two preceding it. If none exists, return 0.
Input
A strictly increasing array arr of positive integers.
Output
An integer: the length of the longest Fibonacci-like subsequence, or 0.
Constraints
- 3 <= arr.length <= 1000
- 1 <= arr[i] < arr[i+1] <= 10^9
Examples
Example 1
Input
arr = [1,2,3,4,5,6,7,8]
Output
5
[1,2,3,5,8] is Fibonacci-like with length 5.
Example 2
Input
arr = [1,3,7,11,12,14,18]
Output
3
[1,11,12], [3,11,14], [7,11,18] etc. give length 3.