We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Length of Longest Fibonacci Subsequence

Difficulty: Medium

Problem Description

Given a strictly increasing array of positive integers, return the length of the longest Fibonacci-like subsequence of the array. If one does not exist, return 0. A sequence is Fibonacci-like if it has at least three elements and satisfies the condition that the sum of any two consecutive elements equals the next element in the sequence.

Key Insights

  • A Fibonacci-like sequence must contain at least three elements.
  • The condition for a Fibonacci-like sequence is that for indices i, j, k, the relationship arr[i] + arr[j] = arr[k] must hold.
  • Since the array is strictly increasing, we can efficiently use a hash map to store indices of elements for quick lookups.
  • Dynamic programming can be employed to find the length of the longest Fibonacci-like subsequence.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

To solve the problem, we can use a dynamic programming approach combined with a hash map for efficient lookups. The main idea is to iterate over all pairs of numbers in the array and check if their sum exists in the array, which would allow us to extend a Fibonacci-like sequence.

  1. Create a hash map to store the indices of each number in the array for O(1) lookups.
  2. Use a 2D array (or a dictionary) to keep track of the lengths of Fibonacci-like subsequences ending at each pair of indices.
  3. Loop through all pairs of indices (i, j) in the array, and for each pair, calculate the potential next number in the sequence (arr[i] + arr[j]).
  4. If this number exists in the hash map, update the length of the Fibonacci-like sequence ending at that index.
  5. The maximum length found across all pairs will be the answer.

Code Solutions

def lenLongestFibSubseq(arr):
    index = {x: i for i, x in enumerate(arr)}
    n = len(arr)
    longest = {}
    max_length = 0

    for j in range(n):
        for i in range(j):
            k = arr[i] + arr[j]
            if k in index:
                longest[(i, j)] = longest.get((index[arr.index(k)], i), 2) + 1
                max_length = max(max_length, longest[(i, j)])
    
    return max_length if max_length >= 3 else 0
← Back to All Questions