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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Length of Longest Fibonacci Subsequence

Number: 905

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Bloomberg, Microsoft, Baidu

Problem Description

Given a strictly increasing array arr of positive integers, find the length of the longest subsequence that is Fibonacci-like. A Fibonacci-like sequence has at least 3 numbers and each subsequent number is the sum of the previous two. If no such subsequence exists, return 0.

Key Insights

  • The array is strictly increasing, which enables binary search or hash mapping techniques.
  • We can use dynamic programming to record the length of the Fibonacci-like sequence ending with any two numbers.
  • A hash map is used to quickly determine if a needed previous number exists in the sequence.
  • The recurrence relation: if arr[k] = arr[j] - arr[i] exists (with k < i) then dp[i][j] = dp[k][i] + 1, else start with length 2 for pairs.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n^2) (in the worst-case scenario for the DP table and O(n) for the hash map)

Solution

We solve this problem using dynamic programming along with a hash map. The idea is to maintain a 2D DP table where dp[i][j] represents the length of the Fibonacci-like sequence ending with arr[i] and arr[j]. For every pair (i, j), we check if there exists an index k such that arr[k] equals arr[j] - arr[i] and k < i. If such an index exists, then we can extend the sequence represented by dp[k][i] by one, thereby updating dp[i][j] to dp[k][i] + 1. We traverse through all possible pairs and update our result accordingly. Finally, if the longest sequence found has a length of 2 or less (which means no valid sequence was found), we return 0; otherwise, we return the maximum length found.

Code Solutions

# Python solution

def lenLongestFibSubseq(arr):
    # Dictionary to map each number to its index for quick lookup
    index_map = {x: i for i, x in enumerate(arr)}
    n = len(arr)
    # DP table: dp[i][j] is length of Fibonacci-like sequence ending with arr[i] and arr[j]
    dp = [[2] * n for _ in range(n)]
    max_len = 0
    
    # Iterate over each pair (i, j) with i < j
    for j in range(n):
        for i in range(j):
            # Calculate the potential previous number in the sequence
            prev = arr[j] - arr[i]
            # Check if such number exists and is less than arr[i]
            if prev < arr[i] and prev in index_map:
                k = index_map[prev]
                dp[i][j] = dp[k][i] + 1
                max_len = max(max_len, dp[i][j])
    # If no valid sequence was found, return 0
    return max_len if max_len >= 3 else 0

# Example usage:
arr = [1,2,3,4,5,6,7,8]
print(lenLongestFibSubseq(arr))  # Output: 5
← Back to All Questions