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 in nums will be between 1 and 65,535.
• k will be between 1 and ⌊length of nums / 3⌋.

Approach

The problem can be solved using dynamic programming. The approach is as follows:

1. Compute the accumulated sum for each sliding window of size k. Let's call this array sums.
2. Compute two lists l and r, where l[i] is the index in [0..i] that maximizes sums[i], and r[i] is the index in [i..n] that maximizes sums[i].
3. Iterate over i from k to n - k, and maintain the maximum sum of sums[l[i - k]], sums[i] and sums[r[i + k]].
4. 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 given nums.
• Two arrays, l and r, 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 from 0 to nums.length, add nums[i] to sum.
• If i is larger or equal to k, subtract nums[i - k] from sum.
• If i is larger or equal to k - 1, set sums[i - k + 1] to sum.
• After that, iterate through the sums array to find l and r. l[i] is assigned the index of the largest value in sums[0..i], and r[i] is assigned the index of the largest value in sums[i..length], where length is the length of nums array.
• And at last, iterate through every i from k to nums.length - k, and assign (l[i - k], i, r[i + k]) to ans 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.