Length of Longest Fibonacci Subsequence
We need to find the length of the longest Fibonaccilike subsequence from a given strictly increasing array of positive integers. A Fibonaccilike 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 Fibonaccilike 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 Fibonaccilike 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 Fibonaccilike 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 Fibonaccilike 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 nonFibonaccilike subsequences (such as
[2, 2, 4]
), we check thatarr[i] + arr[j]
is not equal to2 * arr[j]
.