873. Length of Longest Fibonacci Subsequence

[mah-shamim]

Topics: Array, Hash Table, Dynamic Programming

A sequence x1, x2, ..., xn is Fibonacci-like if:

• n >= 3
• xi + xi+1 == xi+2 for all i + 2 <= 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 <= arr.length <= 1000
• 1 <= arr[i] < arr[i + 1] <= 109

[mah-shamim]

We need to find the length of the longest Fibonacci-like subsequence in a strictly increasing array. A Fibonacci-like sequence is defined such that each element after the first two is the sum of the two preceding ones.

Approach

1. Dynamic Programming (DP) with Hash Map:

   • Hash Map: Use a hash map to store the indices of elements for quick lookup. This allows us to check if the difference between two elements (which would be the preceding element in a Fibonacci sequence) exists in the array.
   • DP Table: Use a 2D DP array where dp[j][k] represents the length of the longest Fibonacci-like subsequence ending with elements at indices j and k. Initialize all elements to 2 since any two elements can start a potential sequence.

2. Iterate Over Pairs:

   • For each pair of indices (j, k) where j < k, check if there exists an element i such that arr[i] + arr[j] = arr[k]. If such an element exists and i < j, update the DP value for dp[j][k] based on the DP value of dp[i][j].

3. Track Maximum Length:

   • Keep track of the maximum length of the subsequence found during the iteration. If no valid subsequence of length 3 or more is found, return 0.

Let's implement this solution in PHP: 873. Length of Longest Fibonacci Subsequence

<?php
/**
 * @param Integer[] $arr
 * @return Integer
 */
function lenLongestFibSubseq($arr) {
    $n = count($arr);
    if ($n < 3) return 0;

    $valueMap = array();
    // Store indices of values in arr for quick lookup
    foreach ($arr as $i => $val) {
        $valueMap[$val] = $i;
    }

    $max = 0;
    $dp = array_fill(0, $n, array_fill(0, $n, 2));

    // Dynamic programming approach
    for ($k = 0; $k < $n; $k++) {
        for ($j = 0; $j < $k; $j++) {
            $diff = $arr[$k] - $arr[$j]; // Previous term in Fibonacci sequence
            if (isset($valueMap[$diff])) {
                $i = $valueMap[$diff];
                if ($i < $j) {
                    $dp[$j][$k] = $dp[$i][$j] + 1;
                    if ($dp[$j][$k] > $max) {
                        $max = $dp[$j][$k];
                    }
                }
            }
        }
    }

    return $max >= 3 ? $max : 0;
}

// Example test cases
$arr1 = [1,2,3,4,5,6,7,8];
echo lenLongestFibSubseq($arr1) . "\n"; // Output: 5

$arr2 = [1,3,7,11,12,14,18];
echo lenLongestFibSubseq($arr2) . "\n"; // Output: 3
?>

Explanation:

• Hash Map Initialization: We first create a hash map to store the indices of the elements in the array. This allows O(1) time complexity for checking the existence of elements.
• DP Array Initialization: The DP array is initialized to 2 for all pairs since any two elements can form the start of a potential sequence.
• Iterate Over Pairs: For each pair (j, k), we compute the difference to check if it exists in the array. If it does and the index of the difference is less than j, we update the DP value for (j, k) based on the DP value of (i, j).
• Track Maximum Length: During the iteration, we keep track of the maximum length of any valid subsequence found. If the maximum length is at least 3, we return it; otherwise, we return 0.

This approach efficiently checks all possible pairs and uses dynamic programming to build up the solution, resulting in an O(n^2) time complexity and O(n^2) space complexity, which is feasible for the given problem constraints.

[kovatz]

Thanks for solving the problem of "Length of Longest Fibonacci Subsequence"

[mah-shamim]

Thanks