Leetcode 689. Maximum Sum of 3 Non-Overlapping Subarrays
Problem Description
Given an array nums
of positive integers, the task is to find three non-overlapping subarrays each of size k
such that the sum of all 3 * k
elements is maximized. The function should return a list of indices representing the starting position of each interval (0-indexed). If multiple answers exist, return the lexicographically smallest one.
Example:
Input: nums = [1, 2, 1, 2, 6, 7, 5, 1]
and k = 2
Output: [0, 3, 5]
Explanation: Here, the 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.
Constraints:
- The length of
nums
will be between 1 and 20,000. - Each element
i
innums
will be between 1 and 65,535. k
will be between 1 and โlength ofnums
/ 3โ.
Approach
The problem can be solved using dynamic programming. The approach is as follows:
- Compute the accumulated sum for each sliding window of size
k
. Let's call this arraysums
. - Compute two lists
l
andr
, wherel[i]
is the index in[0..i]
that maximizessums[i]
, andr[i]
is the index in[i..n]
that maximizessums[i]
. - Iterate over
i
fromk
ton - k
, and maintain the maximum sum ofsums[l[i - k]]
,sums[i]
andsums[r[i + k]]
. - Return the indices of the maximum sum.
An ASCII illustration of the first few steps is shown below:
1 2 3nums: [1, 2, 1, 2, 6, 7, 5, 1] 4k: 2 5sums: [3, 3, 3, 8,13,12, 6] 6l: [0, 0, 0, 3, 4, 4, 4] 7r: [4, 4, 4, 4, 5, 6, 6]
In this example, the maximum sum comes from sums[l[1]] + sums[3] + sums[r[5]]
, which corresponds to the indices [0, 3, 5]
.
Solutions
Now, let's see the solutions in multiple languages.
Python
1 2python 3from typing import List 4 5class Solution: 6 def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]: 7 n = len(nums) - k + 1 8 sums = [0] * n # sums[i]: sum of nums[i..i+k] 9 l = [0] * n # l[i]: index in [0..i] with max sums[i] 10 r = [0] * n # r[i]: index in [i..n) with max sums[i] 11 12 current_sum = 0 13 for i in range(len(nums)): 14 current_sum += nums[i] 15 if i >= k: 16 current_sum -= nums[i - k] 17 if i >= k - 1: 18 sums[i - k + 1] = current_sum 19 20 for i in range(1, n): 21 l[i] = i if sums[i] > sums[l[i - 1]] else l[i - 1] 22 23 r[n - 1] = n - 1 24 for i in range(n - 2, -1, -1): 25 r[i] = i if sums[i] >= sums[r[i + 1]] else r[i + 1] 26 27 ans = [] 28 for i in range(k, n - k): 29 if not ans or sums[l[i - k]] + sums[i] + sums[r[i + k]] > sums[ans[0]] + sums[ans[1]] + sums[ans[2]]: 30 ans = [l[i - k], i, r[i + k]] 31 32 return ans
Java
1 2java 3public class Solution { 4 public int[] maxSumOfThreeSubarrays(int[] nums, int k) { 5 int n = nums.length - k + 1; 6 int[] sums = new int[n], l = new int[n], r = new int[n]; 7 int sum = 0; 8 9 for (int i = 0; i < nums.length; i++) { 10 sum += nums[i]; 11 if (i >= k) 12 sum -= nums[i - k]; 13 if (i >= k - 1) 14 sums[i - k + 1] = sum; 15 } 16 17 for (int i = 1; i < n; i++) 18 l[i] = sums[i] > sums[l[i - 1]] ? i : l[i - 1]; 19 20 r[n - 1] = n - 1; 21 for (int i = n - 2; i >= 0; i--) 22 r[i] = sums[i] >= sums[r[i + 1]] ? i : r[i + 1]; 23 24 int[] ans = new int[]{0, 0, 0}; 25 for (int i = k; i < n - k; i++) 26 if (sums[l[i - k]] + sums[i] + sums[r[i + k]] > sums[ans[0]] + sums[ans[1]] + sums[ans[2]]) 27 ans = new int[]{l[i - k], i, r[i + k]}; 28 29 return ans; 30 } 31}
C++
1 2cpp 3class Solution { 4public: 5 vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) { 6 int n = nums.size() - k + 1; 7 vector<int> sums(n, 0), l(n, 0), r(n, 0); 8 int sum = 0; 9 10 for (int i = 0; i < nums.size(); ++i) { 11 sum += nums[i]; 12 if (i >= k) sum -= nums[i - k]; 13 if (i >= k - 1) sums[i - k + 1] = sum; 14 } 15 16 for (int i = 1; i < n; ++i){ 17 l[i] = sums[i] > sums[l[i - 1]] ? i : l[i - 1]; 18 } 19 20 r[n - 1] = n - 1; 21 for (int i = n - 2; i >= 0; --i){ 22 r[i] = sums[i] >= sums[r[i + 1]] ? i : r[i + 1]; 23 } 24 25 vector<int> ans(3, 0); 26 for (int i = k; i < n - k; ++i) 27 if (sums[l[i - k]] + sums[i] + sums[r[i + k]] > sums[ans[0]] + sums[ans[1]] + sums[ans[2]]) 28 ans = {l[i - k], i, r[i + k]}; 29 30 return ans; 31 } 32};
JavaScript
1 2javascript 3var maxSumOfThreeSubarrays = function(nums, k) { 4 var n = nums.length - k + 1; 5 var sums = Array(n).fill(0); 6 var l = Array(n).fill(0); 7 var r = Array(n).fill(0); 8 var sum = 0; 9 10 for (var i = 0; i < nums.length; i++) { 11 sum += nums[i]; 12 if (i >= k) sum -= nums[i - k]; 13 if (i >= k - 1) sums[i - k + 1] = sum; 14 } 15 16 for (var i = 1; i < n; i++) { 17 l[i] = sums[i] > sums[l[i - 1]] ? i : l[i - 1]; 18 } 19 20 r[n - 1] = n - 1; 21 for (i = n - 2; i >= 0; i--) { 22 r[i] = sums[i] >= sums[r[i + 1]] ? i : r[i + 1]; 23 } 24 25 var ans = [0, 0, 0]; 26 for (i = k; i < n - k; i++) { 27 if (sums[l[i - k]] + sums[i] + sums[r[i + k]] > sums[ans[0]] + sums[ans[1]] + sums[ans[2]]) { 28 ans = [l[i - k], i, r[i + k]]; 29 } 30 } 31 32 return ans; 33};
C#
1 2csharp 3public class Solution { 4 public int[] MaxSumOfThreeSubarrays(int[] nums, int k) { 5 int n = nums.Length - k + 1; 6 int[] sums = new int[n], l = new int[n], r = new int[n]; 7 int sum = 0; 8 9 for (int i = 0; i < nums.Length; i++) { 10 sum += nums[i]; 11 if (i >= k) 12 sum -= nums[i-k]; 13 if (i >= k - 1) 14 sums[i - k + 1] = sum; 15 } 16 17 for (int i = 1; i < n; i++) 18 l[i] = sums[i] > sums[l[i-1]] ? i : l[i-1]; 19 20 r[n - 1] = n - 1; 21 for (int i = n - 2; i >= 0; i--) 22 r[i] = sums[i] >= sums[r[i+1]] ? i : r[i+1]; 23 24 int[] ans = new int[3]; 25 for (int i = k; i < n - k; i++) 26 if (sums[ans[0]] + sums[ans[1]] + sums[ans[2]] < sums[l[i-k]] + sums[i] + sums[r[i+k]]) 27 ans = new int[]{l[i-k], i, r[i+k]}; 28 29 return ans; 30 } 31}
In correspondence with the approaches mentioned above, each of these solutions is leveraging the dynamic programming concept to optimize this.
The aforementioned code snippets in Python, Java, JavaScript, C++ and C# have been implemented in a similar approach.
They each begin by initializing:
- An array to hold the sum for each
k
range values in the givennums
. - Two arrays,
l
andr
, to hold the index that gives the maximum sum in the range[0..i]
and[i..n]
respectively.
The next step in each of the solutions is to compute the sum of the array for each k
range values. After which, for every i
in the range [k..n-k]
, the maximum sum of three sub-arrays is calculated. If the sum is greater than the current maximum, they update the ans
array which will hold the beginning indices of the three sub-arrays.
Here's how it roughly works:
- For all
i
from0
tonums.length
, addnums[i]
tosum
. - If
i
is larger or equal tok
, subtractnums[i - k]
fromsum
. - If
i
is larger or equal tok - 1
, setsums[i - k + 1]
tosum
. - After that, iterate through the
sums
array to findl
andr
.l[i]
is assigned the index of the largest value insums[0..i]
, andr[i]
is assigned the index of the largest value insums[i..length]
, wherelength
is the length ofnums
array. - And at last, iterate through every
i
fromk
tonums.length - k
, and assign(l[i - k], i, r[i + k])
toans
if the sum of values at these indexes is greater than the previous triple.
All five solutions are similar and grasp on a simple yet powerful dynamic programming trick, to effectively extract the maximum sum possible, across three non-overlapping subarrays each of size k
. The codes are efficient and operate at a time complexity of approximately O(n)
, where n
is the length of the given nums
array. Hence, even for large inputs, these solutions will perform well, providing both correct and efficient results.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.