Problem Description

Given a strictly increasing array of positive integers arr, your task is to find the length of the longest subsequence of arr that forms a Fibonacci-like sequence. A sequence is Fibonacci-like if:

• It has at least 3 elements.
• Each element (starting from the third) is the sum of the two preceding elements, i.e., for a sequence X1, X2, ..., Xk, Xi = Xi-1 + Xi-2 for all i ≥ 3.

Return the length of the longest such subsequence in arr. If one does not exist, return 0.

Constraints:

• 3 ≤ arr.length ≤ 1000
• 1 ≤ arr[i] < 10^9
• All elements in arr are unique and strictly increasing.

Thought Process

The problem asks us to look for the longest subsequence that behaves like a Fibonacci sequence. At first glance, you might think of checking all possible subsequences, but that's computationally expensive because the number of subsequences grows exponentially with the array size.

Instead, we notice that any Fibonacci-like sequence is uniquely determined by its first two numbers. Once those are fixed, the rest of the sequence (if possible) is determined. So, for each pair of numbers in arr, we can try to build the longest Fibonacci-like sequence starting with that pair.

To check if a number exists in the array, we need fast lookups. This suggests using a set or a hash map. We also need to avoid recomputation, so dynamic programming or memoization can help us here.

Solution Approach

We will use a dynamic programming approach with hash maps for fast lookups:

1. Index Mapping: First, create a mapping from each number in arr to its index. This allows us to efficiently check if a particular sum exists in the array.
2. DP Table: Use a 2D DP table dp[i][j], where dp[i][j] represents the length of the longest Fibonacci-like subsequence ending with arr[i] and arr[j] (with i < j).
3. Iteration: For every possible pair of indices (i, j) with i < j, compute the possible previous number in the sequence as arr[j] - arr[i]. If this number exists in the array at index k < i, then dp[i][j] = dp[k][i] + 1. Otherwise, set dp[i][j] = 2 (the minimal length for a sequence starting with this pair).
4. Track Maximum: Keep track of the maximum value in the DP table that is at least 3 (since a valid Fibonacci-like sequence must have at least 3 numbers).
5. Return Result: If no such sequence is found, return 0.

This approach efficiently finds the longest Fibonacci-like subsequence by leveraging dynamic programming and hash maps for fast lookups.

Example Walkthrough

Let's walk through an example with arr = [1, 3, 7, 11, 12, 14, 18]:

1. For each pair, say (1, 11), we check if 11 - 1 = 10 exists in arr. It doesn't, so we move on.
2. Try (3, 11): 11 - 3 = 8 not in arr.
3. Try (7, 11): 11 - 7 = 4 not in arr.
4. Try (7, 14): 14 - 7 = 7 (found at index 2, but index must be less than 2, which is not possible here), so skip.
5. Try (11, 18): 18 - 11 = 7 (7 is at index 2, which is less than 3). Now, check dp[2][3], which is 2 by default, so dp[3][6] = 3.
6. Continue this process for all pairs. For (7, 11) and then (11, 18), you can chain the sequence: 7, 11, 18.
7. The longest chain you can build here is 3: [7, 11, 18].

The answer for this example is 3.

Time and Space Complexity

• Brute-force: Trying all possible subsequences has exponential time complexity, specifically O(2^n), which is not feasible for n up to 1000.
• Optimized DP Approach:
  • We examine all pairs (i, j), so O(n^2) pairs.
  • For each pair, all operations (lookup, DP update) are O(1) due to hash maps.
  • Total Time Complexity: O(n^2)
  • Space Complexity: O(n^2) for the DP table, plus O(n) for the hash map.

Summary

To solve the Length of Longest Fibonacci Subsequence problem, we leveraged the fact that a Fibonacci-like sequence is determined by its first two elements. By using a dynamic programming table and a hash map for fast lookups, we efficiently built up possible sequences and tracked the maximum length found. The approach is both time and space efficient for the given constraints, and demonstrates the power of combining DP with hash-based data structures.

Code Implementation

class Solution:
    def lenLongestFibSubseq(self, arr):
        index = {x: i for i, x in enumerate(arr)}
        n = len(arr)
        dp = [[2] * n for _ in range(n)]
        maxlen = 0
        for j in range(n):
            for i in range(j):
                prev = arr[j] - arr[i]
                k = index.get(prev)
                if k is not None and k < i:
                    dp[i][j] = dp[k][i] + 1
                    maxlen = max(maxlen, dp[i][j])
        return maxlen if maxlen >= 3 else 0
      

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        unordered_map<int, int> index;
        for (int i = 0; i < n; ++i) index[arr[i]] = i;
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int maxlen = 0;
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < j; ++i) {
                int prev = arr[j] - arr[i];
                if (index.count(prev)) {
                    int k = index[prev];
                    if (k < i) {
                        dp[i][j] = dp[k][i] + 1;
                        maxlen = max(maxlen, dp[i][j]);
                    }
                }
            }
        }
        return maxlen >= 3 ? maxlen : 0;
    }
};
      

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        Map<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < n; ++i) index.put(arr[i], i);
        int[][] dp = new int[n][n];
        for (int[] row : dp) Arrays.fill(row, 2);
        int maxlen = 0;
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < j; ++i) {
                int prev = arr[j] - arr[i];
                if (index.containsKey(prev)) {
                    int k = index.get(prev);
                    if (k < i) {
                        dp[i][j] = dp[k][i] + 1;
                        maxlen = Math.max(maxlen, dp[i][j]);
                    }
                }
            }
        }
        return maxlen >= 3 ? maxlen : 0;
    }
}
      

var lenLongestFibSubseq = function(arr) {
    const n = arr.length;
    const index = new Map();
    for (let i = 0; i < n; ++i) index.set(arr[i], i);
    const dp = Array.from({length: n}, () => Array(n).fill(2));
    let maxlen = 0;
    for (let j = 0; j < n; ++j) {
        for (let i = 0; i < j; ++i) {
            let prev = arr[j] - arr[i];
            if (index.has(prev)) {
                let k = index.get(prev);
                if (k < i) {
                    dp[i][j] = dp[k][i] + 1;
                    maxlen = Math.max(maxlen, dp[i][j]);
                }
            }
        }
    }
    return maxlen >= 3 ? maxlen : 0;
};