689. Maximum Sum of 3 Non-Overlapping Subarrays

Description

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)

 

Solutions

Solution: Prefix Sum + Dynamic Programming

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
const maxSumOfThreeSubarrays = function (nums, k) {
  const n = nums.length;
  const prefixSum = new Array(n).fill(0);
  const leftDp = new Array(n).fill(0);
  const rightDp = new Array(n).fill(n - k);

  prefixSum[-1] = 0;

  for (let index = 0; index < n; index++) {
    prefixSum[index] = prefixSum[index - 1] + nums[index];
  }
  const getSubSum = index => prefixSum[index + k - 1] - prefixSum[index - 1];
  let maxSum = prefixSum[k - 1];

  for (let index = 1; index < n; index++) {
    const currentSum = getSubSum(index);

    if (currentSum > maxSum) {
      maxSum = currentSum;
      leftDp[index] = index;
      continue;
    }
    leftDp[index] = leftDp[index - 1];
  }
  maxSum = prefixSum[n - 1] - prefixSum[n - k - 1];

  for (let index = n - k - 1; index >= 0; index--) {
    const currentSum = getSubSum(index);

    if (currentSum >= maxSum) {
      maxSum = currentSum;
      rightDp[index] = index;
      continue;
    }
    rightDp[index] = rightDp[index + 1];
  }
  let result = [];

  maxSum = 0;

  for (let index = k; index <= n - k * 2; index++) {
    const left = leftDp[index - k];
    const right = rightDp[index + k];
    const sum = getSubSum(left) + getSubSum(index) + getSubSum(right);

    if (sum <= maxSum) continue;
    result = [left, index, right];
    maxSum = sum;
  }
  return result;
};