689. Maximum Sum of 3 Non-Overlapping Subarrays

[mah-shamim]

Topics: Array, Dynamic Programming

Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example 1:

• Input: nums = [1,2,1,2,6,7,5,1], k = 2
• Output: [0,3,5]
• Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
  We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

Example 2:

• Input: nums = [1,2,1,2,1,2,1,2,1], k = 2
• Output: [0,2,4]

Constraints:

• 1 <= nums.length <= 2 * 104
• 1 <= nums[i] < 216
• 1 <= k <= floor(nums.length / 3)

[mah-shamim]

We will use a dynamic programming approach. The idea is to break down the problem into smaller subproblems, leveraging the overlap of subarrays to efficiently calculate the maximum sum of three non-overlapping subarrays of length k.

Approach:

1. Precompute the sums of subarrays of length k:
   First, we compute the sum of all subarrays of length k in the input array nums. This can be done efficiently in linear time by using a sliding window technique.

2. Dynamic Programming (DP):
   We create two auxiliary arrays, left and right, to store the indices of the best subarrays found up to the current position. The left[i] will store the index of the best subarray ending before index i, and right[i] will store the index of the best subarray starting after index i.

3. Iterate and Calculate the Maximum Sum:
   For each possible middle subarray starting at index j, we calculate the total sum by considering the best left subarray before j and the best right subarray after j.

4. Lexicographical Ordering:
   If there are multiple valid answers (with the same sum), we return the lexicographically smallest one. This is ensured by the order of iteration.

Let's implement this solution in PHP: 689. Maximum Sum of 3 Non-Overlapping Subarrays

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer[]
 */
function maxSumOfThreeSubarrays($nums, $k) {
    $n = count($nums);

    // Step 1: Calculate all the subarray sums of length k
    $sum = [];
    $windowSum = 0;
    for ($i = 0; $i < $k; $i++) {
        $windowSum += $nums[$i];
    }
    $sum[0] = $windowSum;
    for ($i = $k; $i < $n; $i++) {
        $windowSum += $nums[$i] - $nums[$i - $k];
        $sum[$i - $k + 1] = $windowSum;
    }

    // Step 2: Dynamic programming for left and right max sums
    $left = [];
    $right = [];
    $leftMaxSum = 0;
    for ($i = 0; $i < $n - $k + 1; $i++) {
        if ($sum[$i] > $sum[$leftMaxSum]) {
            $leftMaxSum = $i;
        }
        $left[$i] = $leftMaxSum;
    }

    $rightMaxSum = $n - $k;
    for ($i = $n - $k; $i >= 0; $i--) {
        if ($sum[$i] >= $sum[$rightMaxSum]) {
            $rightMaxSum = $i;
        }
        $right[$i] = $rightMaxSum;
    }

    // Step 3: Find the best middle subarray and combine with left and right
    $maxSum = 0;
    $result = [];
    for ($j = $k; $j <= $n - 2 * $k; $j++) {
        $i = $left[$j - $k];
        $l = $right[$j + $k];
        $totalSum = $sum[$i] + $sum[$j] + $sum[$l];
        if ($totalSum > $maxSum) {
            $maxSum = $totalSum;
            $result = [$i, $j, $l];
        }
    }

    return $result;
}

// Test cases
print_r(maxSumOfThreeSubarrays([1,2,1,2,6,7,5,1], 2)); // [0, 3, 5]
print_r(maxSumOfThreeSubarrays([1,2,1,2,1,2,1,2,1], 2)); // [0, 2, 4]
?>

Explanation:

1. Subarray Sums Calculation:

   • We calculate the sum of all possible subarrays of length k. This is done by first calculating the sum of the first k elements. Then, for each subsequent position, we subtract the element that is left behind and add the next element in the array, making it an efficient sliding window approach.

2. Left and Right Arrays:

   • left[i] holds the index of the subarray with the maximum sum that ends before index i.
   • right[i] holds the index of the subarray with the maximum sum that starts after index i.

3. Final Calculation:

   • For each middle subarray j, we check the combination of the best left subarray and the best right subarray, and update the result if the sum is greater than the current maximum.

4. Lexicographically Smallest Answer:

   • As we iterate from left to right, we ensure the lexicographically smallest solution by naturally choosing the first subarrays that yield the maximum sum.

Example:

For the input:

$nums = [1, 2, 1, 2, 6, 7, 5, 1];
$k = 2;

The output will be:

[0, 3, 5]

This approach ensures that the time complexity remains efficient, with a time complexity of approximately O(n), where n is the length of the input array nums.

[topugit]

Thanks to solve the "Maximum Sum of 3 Non-Overlapping Subarrays" problem

[mah-shamim]

Thanks