Length of Longest Fibonacci Subsequence
We need to find the length of the longest Fibonacci-like subsequence from a given strictly increasing array of positive integers. A Fibonacci-like sequence follows the property that each element is the sum of the previous two elements.
We’ll implement a dynamic programming approach to solve this problem:
Use a Dictionary: We’ll use a dictionary
index
to map each value in the array to its index. This will help us quickly look up the index of any value.Initialize Dynamic Programming Table: We’ll use a 2D table
dp
wheredp[i][j]
represents the length of the longest Fibonacci-like subsequence that ends witharr[i]
andarr[j]
.Iterate Through Pairs: For each pair
(i, j)
withi < j
, we’ll check ifarr[i] + arr[j]
is inarr
and is a Fibonacci-like continuation of the subsequence ending inarr[i]
andarr[j]
. If it is, we’ll updatedp[j][k]
, wherek
is the index ofarr[i] + arr[j]
.Find Maximum Length: We’ll go through the
dp
table and find the maximum length of any Fibonacci-like subsequence.
Below is the code snippet for the above approach:
|
|
Example:
- Input:
arr = [1,2,3,4,5,6,7,8]
- Output:
5
- Explanation: The longest subsequence that is Fibonacci-like is
[1,2,3,5,8]
.
Insights:
- Time Complexity: The code runs in (O(n^2)) time, where (n) is the length of the input array.
- Space Complexity: The space complexity is (O(n^2)), as we use a 2D table to store the dynamic programming states.
- Use of Dynamic Programming: By breaking the problem down into subproblems and storing the results of those subproblems, we can efficiently solve the original problem.
- Checking Continuation: To avoid non-Fibonacci-like subsequences (such as
[2, 2, 4]
), we check thatarr[i] + arr[j]
is not equal to2 * arr[j]
.