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:

  1. 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.

  2. Initialize Dynamic Programming Table: We’ll use a 2D table dp where dp[i][j] represents the length of the longest Fibonacci-like subsequence that ends with arr[i] and arr[j].

  3. Iterate Through Pairs: For each pair (i, j) with i < j, we’ll check if arr[i] + arr[j] is in arr and is a Fibonacci-like continuation of the subsequence ending in arr[i] and arr[j]. If it is, we’ll update dp[j][k], where k is the index of arr[i] + arr[j].

  4. 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n = len(arr)
        index = {x: i for i, x in enumerate(arr)}
        dp = collections.defaultdict(lambda: 2)
        maxLength = 0

        for j in range(n):
            for i in range(j):
                if arr[i] + arr[j] in index and arr[i] + arr[j] != 2 * arr[j]:
                    k = index[arr[i] + arr[j]]
                    dp[j, k] = dp[i, j] + 1
                    maxLength = max(maxLength, dp[j, k])

        return maxLength if maxLength >= 3 else 0

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 that arr[i] + arr[j] is not equal to 2 * arr[j].