Maximum Sum of 3 Non-Overlapping Subarrays

Problem

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 * 10⁴
1 <= nums[i] < 2¹⁶
1 <= k <= floor(nums.length / 3)

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSumOfThreeSubarrays = function(nums, k) {
    // populate cache
    const cache = []; // cache[i] is sum(nums[i:i + k])
    let sum = 0;

    for (let i = 0; i < k; i++) { // sum of first k values
        sum += nums[i];
    }

    cache.push(sum);
    for (let i = 1; i <= nums.length - k; i++) {
        sum -= nums[i - 1];
        sum += nums[i + k - 1];
        cache.push(sum);
    }

    // populate dpL and dpR
    const dpL = []; // dpL[i] is the index of cache[0:i + 1] that has the max value
    const dpR = []; // dpR[i] is the index of cache[i:cache.length] that has the max value

    // base case
    dpL[0] = 0;
    dpR[cache.length - 1] = cache.length - 1;

    // recursive case
    for (let i = 1; i < cache.length; i++) {
        if (cache[i] > cache[dpL[i - 1]]) {
            dpL[i] = i;
        } else {
            dpL[i] = dpL[i - 1];
        }
    }

    for (let i = cache.length - 2; i >= 0; i--) {
        if (cache[i] >= cache[dpR[i + 1]]) {
            dpR[i] = i;
        } else {
            dpR[i] = dpR[i + 1];
        }
    }

    // find starting index of the three intervals with max sum
    let res = null;
    let maxSum = -Infinity;
    for (let i = k; i < cache.length - k; i++) {
        const i1 = dpL[i - k]; // interval 1 index
        const i2 = i; // interval 2 index
        const i3 = dpR[i + k]; // interval 3 index
        const curSum = cache[i1] + cache[i2] + cache[i3];

        if (maxSum < curSum) {
            maxSum = curSum;
            res = [i1, i2, i3];
        }
    }
    return res;
};

Observe that if we fix the middle interval at index i, then the first interval must be in nums[0:i] and the last interval must be in nums[i + k:nums.length]. Using DP, we can find the start index of the first interval and last interval in O(1) time that maximizes the sum (provided we fix the starting index of the second interval). This way, we can simply try all O(n) possible starting indices of the second interval and return the triplet with the maximum sum.

To do so, we first create array cache where cache[i] is sum(nums[i:i + k]) (ie. starting from index i, the sum of the next k values including itself). Using cache, we can use DP to fill in arrays dpL and dpR, where:

dpL[i] is the index of cache[0:i + 1] that has the max value (ie. the starting index of the interval in nums[0:i + k] with max sum).
dpR[i] is the index of cache[i:cache.length] that has the max value (ie. the starting index of the interval in nums[i:nums.length] with max sum).

The logic to populate dpL and dpR is trivial. We simply keep either the current index or the previously recorded index based on which has the larger value (ie. sum) in cache.

Thus, given the starting index of the second interval is i, to maximize the sum of the first and last intervals, we should use starting indices dpL[i - k] and dpR[i + k] respectively.

Problem​

Solution​

Problem

Solution