Problem Informations

• Problem Index: 873
• Problem Link: Length of Longest Fibonacci Subsequence
• Topics: Array, Hash Table, Dynamic Programming

Problem Description

A sequence $x_1, x_2, \ldots, x_n$ is Fibonacci-like if:

• $n \geq 3$
• $x_i + x_{i+1} = x_{i+2}$ for all $i + 2 \leq n$

Given a strictly increasing array arr of positive integers forming a sequence, return the length of the longest Fibonacci-like subsequence of arr. If one does not exist, return 0.

A subsequence is derived from another sequence arr by deleting any number of elements (including none) from arr, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].

Example 1:

Input: arr = [1,2,3,4,5,6,7,8]
Output: 5
Explanation: The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:

Input: arr = [1,3,7,11,12,14,18]
Output: 3
Explanation: The longest subsequence that is fibonacci-like: [1,11,12], [3,11,14] or [7,11,18].

Constraints:

• $3 \leq arr.length \leq 1000$
• $1 \leq arr[i] < arr[i + 1] \leq 10^9$

Intuition

The problem requires identifying the longest subsequence in a strictly increasing array that exhibits a Fibonacci-like property. Each subsequence term, starting from the third one, must be the sum of the two preceding terms. The constraint that the given array is strictly increasing simplifies identification of potential predecessors needed to form such a sequence.

The challenge is to efficiently determine pairs of numbers that can form valid Fibonacci-like subsequences. A dynamic programming approach is suitable here, as it can build solutions for longer subsequences based on shorter, previously solved subsequences.

Approach

The approach leverages a dynamic programming (DP) technique to systematically explore potential Fibonacci-like subsequences within the array. Here’s a detailed explanation of the algorithm:

1. Initialization:

   • We define a 2D DP table dp where dp[j][i] will store the length of the longest Fibonacci-like subsequence ending with elements at indices j and i. Initially, each value is set to 2 since any two elements form a trivial subsequence.

2. Iterating through the array:

   • We iterate over each possible endpoint i for our subsequences, starting from the third element in the array (index 2), since a Fibonacci-like sequence requires at least three elements.
   • For each i, we consider all potential second-to-last elements j ranging from i-1 down to 1.

3. Determining the previous element:

   • For each selected pair (j, i), compute the element neededPrev that must exist as the element before j to maintain the Fibonacci property: arr[k] + arr[j] = arr[i]. Hence, neededPrev = arr[i] - arr[j].
   • If neededPrev is not less than arr[j], break out of the loop since all subsequent j will yield a larger neededPrev, violating the increasing order property.

4. Check existence of the previous element:

   • Utilize binary search (lower_bound) within the bounds of potential indices to check if neededPrev exists in the array before index j.
   • If found at index k, it implies arr[k] forms a valid Fibonacci-like property with arr[j] and arr[i].

5. Update the DP table:

   • Update dp[j][i] as dp[k][j] + 1, indicating the current length of Fibonacci-like subsequence up to i.
   • Track the maximum subsequence length encountered during the iterations as maxLength.

6. Result Evaluation:

   • After considering all possible subsequences, return maxLength if it is greater than 2; otherwise, return 0 as no valid subsequence longer than two was found.

This method ensures that we efficiently explore all potential subsequences and effectively capture the longest one with the desired property while adhering to time complexity constraints.

Code

C++

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        
        // Create a 2D DP table initialized to store at least 2 for every pair
        vector<vector<int>> dp(n, vector<int>(n, 2));
        
        // Answer variable to keep track of the max length found
        int maxLength = 0;

        // Iterate over the array from the third element onwards
        for (int i = 2; i < n; i++) {
            // Iterate from the element just before i till the start of the array
            for (int j = i - 1; j > 0; j--) {
                // Compute the previous element needed for Fibonacci property
                int neededPrev = arr[i] - arr[j];
                
                // If the previous element is not smaller than the current element, break
                if (neededPrev >= arr[j]) break;
                
                // Find the position of the previous element in the array
                auto it = lower_bound(arr.begin(), arr.begin() + j, neededPrev);
                
                // Check if the previous element exists
                if (it != arr.begin() + j && *it == neededPrev) {
                    int k = it - arr.begin(); // Index of the previous element

                    // Update the DP table for (j, i)
                    dp[j][i] = dp[k][j] + 1;
                    
                    // Update maxLength with the length found
                    maxLength = max(maxLength, dp[j][i]);
                }
            }
        }
        
        // If the longest length is greater than two, return it; otherwise, return 0
        return maxLength > 2 ? maxLength : 0;
    }
};

Python

class Solution:
    def lenLongestFibSubseq(self, arr):
        n = len(arr)
        
        # Create a 2D DP table initialized to store at least 2 for every pair
        dp = [[2] * n for _ in range(n)]
        
        # Answer variable to keep track of the max length found
        maxLength = 0

        # Iterate over the array from the third element onwards
        for i in range(2, n):
            # Iterate from the element just before i till the start of the array
            for j in range(i - 1, 0, -1):
                # Compute the previous element needed for Fibonacci property
                neededPrev = arr[i] - arr[j]
                
                # If the previous element is not smaller than the current element, break
                if neededPrev >= arr[j]:
                    break
                
                # Find the position of the previous element in the array
                it = bisect.bisect_left(arr, neededPrev, 0, j)
                
                # Check if the previous element exists
                if it != j and arr[it] == neededPrev:
                    k = it  # Index of the previous element

                    # Update the DP table for (j, i)
                    dp[j][i] = dp[k][j] + 1
                    
                    # Update maxLength with the length found
                    maxLength = max(maxLength, dp[j][i])
        
        # If the longest length is greater than two, return it; otherwise, return 0
        return maxLength if maxLength > 2 else 0

Complexity

• Time complexity: $O(n^2 \log n)$

  The algorithm involves two nested loops iterating over the array arr, with the outer loop running from the third element to the end of the array ($O(n)$ iterations) and the inner loop iterating backward from the current position of the outer loop ($O(n)$ iterations). Inside the inner loop, lower_bound is called to find the required previous element, which in the worst case involves a binary search on up to $j$ elements, giving it a complexity of $O(\log n)$. Thus, the overall time complexity is $O(n^2 \log n)$.

• Space complexity: $O(n^2)$

  The space complexity is dominated by the 2D dynamic programming table dp, which contains $n \times n$ entries. Each entry represents the length of the longest Fibonacci-like subsequence that ends with the elements at indices $j$ and $i$. Therefore, the space complexity is $O(n^2)$.