Algorithm


Problem Name: 689. Maximum Sum of 3 Non-Overlapping Subarrays

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)

Code Examples

#1 Code Example with C Programming

Code - C Programming


const maxSumOfThreeSubarrays = (nums, k) => {
  let n = nums.length,
    maxsum = 0
  let sum = new Array(n + 1).fill(0),
    posLeft = new Array(n).fill(0),
    posRight = new Array(n).fill(0),
    ans = new Array(3).fill(0)
  for (let i = 0; i  <  n; i++) sum[i + 1] = sum[i] + nums[i]
  for (let i = k, tot = sum[k] - sum[0]; i  <  n; i++) {
    if (sum[i + 1] - sum[i + 1 - k] > tot) {
      posLeft[i] = i + 1 - k
      tot = sum[i + 1] - sum[i + 1 - k]
    } else posLeft[i] = posLeft[i - 1]
  }
  posRight[n - k] = n - k
  for (let i = n - k - 1, tot = sum[n] - sum[n - k]; i >= 0; i--) {
    if (sum[i + k] - sum[i] >= tot) {
      posRight[i] = i
      tot = sum[i + k] - sum[i]
    } else posRight[i] = posRight[i + 1]
  }
  for (let i = k; i  < = n - 2 * k; i++) {
    let l = posLeft[i - 1],
      r = posRight[i + k]
    let tot = sum[i + k] - sum[i] + (sum[l + k] - sum[l]) + (sum[r + k] - sum[r])
    if (tot > maxsum) {
      maxsum = tot
      ans[0] = l
      ans[1] = i
      ans[2] = r
    }
  }
  return ans
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1,2,1,2,6,7,5,1], k = 2

Output

x
+
cmd
[0,3,5]

#2 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        // dp[i] is the sum of subarray of in range [i , i + k)
        // nextMax[i] is the maximum value in dp[i : dp.size() - 1]
        // nextIdx[i] is the index of nextMax[i]
        int n = nums.size(), sum = 0, maxRight = 0, idx = 0, maxSum = 0;
        vector<int>res, dp(n - k + 1), nextMax(n - k + 1), nextIdx(n - k + 1);
        // Using a sliding window to get the sum of subarray in range [i , i + k)
        for(int i = 0; i  <  n; i++){
            sum += nums[i];
            if(i >= k) sum -= nums[i - k];
            if(i >= k - 1) dp[i - k + 1] = sum;
        }
        // Starting from end of dp array to get the maximum value after current position
        for(int i = dp.size() - 1; i >= 0; i--){
            if(dp[i] > maxRight) maxRight = dp[i], idx = i;
            nextMax[i] = maxRight;
            nextIdx[i] = idx;
        }
        // Using two pointers i, j to find the result
        // The third entry is determined by nextMax[j + k]
        for(int i = 0; i <= n - 3 * k; i++)
            for(int j = i + k; j  < = n - 2 * k; j++>{
                sum = dp[i] + dp[j] + nextMax[j + k];
                if(sum > maxSum){
                    maxSum = sum;
                    res = {i, j, nextIdx[j + k]};
                }
            }
        return res;
    }
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1,2,1,2,6,7,5,1], k = 2

Output

x
+
cmd
[0,3,5]

#3 Code Example with Javascript Programming

Code - Javascript Programming


const maxSumOfThreeSubarrays = (nums, k) => {
  let n = nums.length,
    maxsum = 0
  let sum = new Array(n + 1).fill(0),
    posLeft = new Array(n).fill(0),
    posRight = new Array(n).fill(0),
    ans = new Array(3).fill(0)
  for (let i = 0; i  <  n; i++) sum[i + 1] = sum[i] + nums[i]
  for (let i = k, tot = sum[k] - sum[0]; i  <  n; i++) {
    if (sum[i + 1] - sum[i + 1 - k] > tot) {
      posLeft[i] = i + 1 - k
      tot = sum[i + 1] - sum[i + 1 - k]
    } else posLeft[i] = posLeft[i - 1]
  }
  posRight[n - k] = n - k
  for (let i = n - k - 1, tot = sum[n] - sum[n - k]; i >= 0; i--) {
    if (sum[i + k] - sum[i] >= tot) {
      posRight[i] = i
      tot = sum[i + k] - sum[i]
    } else posRight[i] = posRight[i + 1]
  }
  for (let i = k; i  < = n - 2 * k; i++) {
    let l = posLeft[i - 1],
      r = posRight[i + k]
    let tot = sum[i + k] - sum[i] + (sum[l + k] - sum[l]) + (sum[r + k] - sum[r])
    if (tot > maxsum) {
      maxsum = tot
      ans[0] = l
      ans[1] = i
      ans[2] = r
    }
  }
  return ans
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1,2,1,2,1,2,1,2,1], k = 2

Output

x
+
cmd
[0,2,4]

#4 Code Example with Python Programming

Code - Python Programming


class Solution:
    def maxSumOfThreeSubarrays(self, nums, k):
        single, double, sm, n, cur = {}, {}, 0, len(nums), sum(nums[:k - 1])
        for i in range(k - 1, n):
            cur += nums[i]
            single[i - k + 1] = cur
            cur -= nums[i - k + 1]
        cur = n - k, single[n - k]
        for i in range(n - k, k * 2 - 1, -1):
            if single[i] >= cur[1]:
                cur = i, single[i]
            double[i - k] = cur[1] + single[i - k], i - k, cur[0]
        cur = double[n - 2 * k]
        for i in range(n - 2 * k, k - 1, -1):
            if double[i][0] >= cur[0]:
                cur = double[i]
            if single[i - k] + cur[0] >= sm:
                sm, res = single[i - k] + cur[0], [i - k, cur[1], cur[2]]
        return res
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1,2,1,2,1,2,1,2,1], k = 2

Output

x
+
cmd
[0,2,4]
Advertisements

Demonstration


Previous
#688 Leetcode Knight Probability in Chessboard Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#690 Leetcode Employee Importance Solution in C, C++, Java, JavaScript, Python, C# Leetcode