689. Maximum Sum of 3 Non-Overlapping Subarrays


Problem Description

The problem presents a situation where we need to find three non-overlapping contiguous subarrays of equal length k within an integer array nums. The goal is to maximize the sum of these subarrays. The output should be the starting indices of the three subarrays that provide this maximum sum. The indices must be in ascending order, forming a list where the index of the first subarray is at the first position, the index of the second at the second position, and the index of the third at the last position. If multiple solutions exist, the one with the lexicographically smallest indices (which means the first few indices as small as possible) should be returned.

Intuition

To solve this type of problem effectively, a good approach would involve dynamic programming or sliding window techniques to optimize computation.

Essentially, we are required to consider three overlapping sets of sliding windows of size k across the array and calculate the sum of elements within these windows. To avoid recalculating the sums repeatedly, one can keep track of the sums of these subarrays as the windows slide across the array.

We break the problem into smaller parts:

  1. Calculate the sum of the subarray ending at the current element for all three positions and maintain the maximum sum encountered so far for each of the first two positions.

  2. Keep track of the indices where these maximum sums occur, as we will need to return the starting positions of the subarrays.

  3. Compare each potential triplet of sums (one from each of the three subarrays being considered) to find the maximum sum and update it accordingly.

The solution involves a single pass through the array, beginning after the point where the third subarray of length k could start, which is at index 2k. We update the sums s1, s2, s3 for each of the subarrays every time we move to the right. When we move to the right, we add the element entering the subarray and subtract the element leaving it, keeping the window size k constant.

By the time we reach index 3k-1, we have enough information to begin considering valid triplets of subarrays. We compare sums to our previously stored maximums and update them and their corresponding indices.

The clever part of this approach is that it looks ahead to calculate potential sums for subarrays and uses a concise state to maintain the best indices seen so far, ensuring we can return the lexicographically smallest solution.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution provided utilizes the sliding window technique, combined with dynamic programming concepts, to efficiently find the maximum sum of three non-overlapping subarrays of length k. Let's go through the approach used in the solution with reference to the code:

  1. Initialize four sum variables s, s1, s2, and s3 to hold the current total sum of all three subarrays and each individual subarray, respectively.

  2. Initialize variables mx1, and mx12 to hold the maximum sum encountered for the first subarray and first two subarrays respectively.

  3. Define variables idx1, idx12, and ans to keep track of the indices of the maximum sums. idx1 is an integer for the start of the first subarray, idx12 is a tuple for the start of the first and second subarrays, and ans is the final answer list containing the starts of all three subarrays.

  4. Iterate through the array starting at k * 2 which is the ending index for the second possible subarray. This allows enough space for the third subarray to fit within the bounds of the array.

  5. In each step of the iteration:

    • Add the current values to the sums s1, s2, and s3 corresponding to windows ending at the current index for the first, second, and third subarray respectively.
    • Once we've reached the end of the third subarray (i >= k * 3 - 1), check and update the maximum sums mx1 and mx12 if we've found a new maximum.
    • Record the beginning indices of these subarrays in idx1 and idx12.
    • Check if the sum of the current three subarrays is greater than the best found so far (s). If so, update s and record the starting indices in the answer list ans.
    • Slide the windows by subtracting the elements that are no longer included in the subarrays s1, s2, and s3.
  6. At each step, you are effectively shifting three sliding windows simultaneously and checking if the current triplet of sums yields a better solution than previously discovered.

  7. After iterating through the entire array, the ans list contains the starting positions of the three subarrays with the maximum sum.

The for loop ensures that we only consider subarrays that are non-overlapping and of size k. By updating potential sums as we move along the array and only keeping track of the best sums and their starting indices, we avoid recalculating the sums unnecessarily.

In summary, this solution efficiently computes the required maximum sum and corresponding subarray indices with just one pass through the array, by applying a dynamic sliding window approach.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example with an array nums and a subarray length k. We'll walk through the solution approach with the given array:

1nums = [4, 5, 10, 6, 11, 17, 4, 11, 1, 3]
2k = 2

Our task is to find three non-overlapping subarrays each of length k, such that their total sum is maximized. Let's follow the solution approach:

  1. Initialize the sum variables s1, s2, and s3 to zero. These will keep track of the sums of the current windows for the first, second, and third subarrays.
  2. Initialize mx1 to zero, and mx12 is also set to zero. These variables will store the maximum sum of the first subarray and the combined first and second subarrays, respectively.
  3. Define idx1 to be -1 (as an initial placeholder), idx12 to be a tuple (-1, -1), and ans to be a list [-1, -1, -1]. These will eventually hold the starting indices of our optimal subarrays.

Now, let's start iterating the array starting at index 4 (k * 2), because this is where the second subarray could end, leaving room for a third:

  • At index 4 (nums[4] = 11), we start considering our windows. The sums would be s1 = nums[2] + nums[3], s2 = nums[2] + nums[3] + nums[4] + nums[5] - nums[2] - nums[3], and s3 is still not considered yet because we haven't reached the end of a possible third window.
  • When i reaches 5, we can start to update s3 as well because we now have enough elements to form the third subarray.
  • Continue this pattern until i reaches 3k - 1 = 5. At this point, we begin to take the maximum of sums found so far, which is mx1, and update idx1 if we've found a new maximum.
  • Every time we move past i = 5, we continue updating mx12 and idx12 with the indices of the first two windows if the sum of s1 and s2 at this point is greater than what's stored in mx12.
  • If we find that s1 + s2 + s3 > s, we update s and store the current indices in ans.

Let's perform these steps with our example array:

  • For i = 4 (the first position we check):

    • s1 = nums[2] + nums[3] = 10 + 6 = 16
    • s2 is not updated yet since we need to reach at least i = 5
    • s3 is not considered yet
  • For i = 5 (now s2 and s3 can be updated):

    • s2 = mx1 + nums[4] + nums[5] = 16 + 11 + 17 = 44
    • s3 is not considered yet since we haven't reached i = k*3 - 1
    • Update mx1 to 16 and idx1 to position 2
    • ans is still [-1, -1, -1]
  • Continue moving to the right and perform the updates. When s1, s2, and s3 can all be updated:

    • For i = 6 (3k - 1):
      • s1 = 27 (for subarray starting at index 3)
      • s2 = 44 (already calculated)
      • s3 = mx12 + nums[5] + nums[6] = 44 + 17 + 4 = 65
      • At this point, idx12 would become (2, 4) as this is the index pair for the maximum sum of the first two subarrays.
      • Now we can compare s1 + s2 + s3 with s and update ans if we find a greater sum. Here, s will become 27 + 44 + 65 = 136 and ans will become [2, 4, 5].
  • As we continue to slide our window to the right, we keep updating the sums s1, s2, and s3 by adding the new element and subtracting the last element of the older subarray:

    • For i = 7:
      • s1 = 17 + 11 = 28 (subarray starting at index 4)
      • s3 now will consider the new maximum of s2 which was 44 and add the sums of the new subarray [nums[6], nums[7]], and so on.

Upon completion of the loop, ans contains the starting indices of the subarrays. Given our array and k, the maximum sum would occur with subarrays starting at indices [1, 3, 5], which we would find following this method to the end. The subarrays are [5, 10], [6, 11], [17, 4] with a total sum of 53.

This walkthrough has exemplified how the sliding window approach combined with dynamic programming principles can be applied to find the maximum sum of three non-overlapping subarrays of fixed length k.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
5        # Initialize the sums of the three subarrays and the maximum sums
6        sum1 = sum2 = sum3 = 0
7        max_sum1 = max_sum1_2 = 0
8        max_index1, max_indices1_2 = 0, ()
9        result = []
10      
11        # Start iterating over the main array from the point where
12        # we could fit three subarrays of length k
13        for i in range(k * 2, len(nums)):
14            # Add the current element to the running sum of each subarray
15            sum1 += nums[i - k * 2]  # sum for the first subarray
16            sum2 += nums[i - k]      # sum for the second subarray
17            sum3 += nums[i]          # sum for the third subarray
18          
19            # Check if we have traversed 'k' elements for each subarray
20            if i >= k * 3 - 1:
21                # Update max_sum1 and max_index1 if sum1 is greater than max_sum1
22                if sum1 > max_sum1:
23                    max_sum1 = sum1
24                    max_index1 = i - k * 3 + 1
25              
26                # Update max_sum1_2 and max_indices1_2 if the combination of sum1 and sum2
27                # provides a bigger sum than current max_sum1_2
28                if max_sum1 + sum2 > max_sum1_2:
29                    max_sum1_2 = max_sum1 + sum2
30                    max_indices1_2 = (max_index1, i - k * 2 + 1)
31              
32                # Update the result if the combination of sum1, sum2, and sum3 
33                # is greater than the overall max sum found so far
34                if max_sum1_2 + sum3 > sum:
35                    sum = max_sum1_2 + sum3
36                    result = [*max_indices1_2, i - k + 1]
37              
38                # Slide the window for each subarray by subtracting the element that's no longer in the window
39                sum1 -= nums[i - k * 3 + 1]
40                sum2 -= nums[i - k * 2 + 1]
41                sum3 -= nums[i - k + 1]
42      
43        # Return the indices of the first elements of the three subarrays
44        return result
45
1class Solution {
2    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
3      
4        // Initialize arrays to store answers and sum variables
5        int[] maxSubarraysIndices = new int[3];
6        int sum1 = 0, sum2 = 0, sum3 = 0; // These hold the sums of the subarrays
7        int maxSum1 = 0, maxSum1And2 = 0; // These hold the max sums encountered so far
8        int maxIndex1 = 0, maxIndex1And2_1 = 0, maxIndex1And2_2 = 0;
9      
10        // Iterate through nums, starting from the end of the third subarray
11        for (int i = k * 2; i < nums.length; ++i) {
12          
13            // Update the rolling sums by adding the new element and subtracting the oldest
14            sum1 += nums[i - k * 2];
15            sum2 += nums[i - k];
16            sum3 += nums[i];
17          
18            // Check if we have seen k*3 elements
19            if (i >= k * 3 - 1) {
20              
21                // Check if current sum1 is the greatest so far
22                if (sum1 > maxSum1) {
23                    maxSum1 = sum1;
24                    maxIndex1 = i - k * 3 + 1;
25                }
26              
27                // Check if the current combination of sum1 and sum2 is the greatest so far
28                if (maxSum1 + sum2 > maxSum1And2) {
29                    maxSum1And2 = maxSum1 + sum2;
30                    maxIndex1And2_1 = maxIndex1;
31                    maxIndex1And2_2 = i - k * 2 + 1;
32                }
33              
34                // Check if the current combination of sum1, sum2, and sum3 is the greatest so far
35                if (maxSum1And2 + sum3 > sum1 + sum2 + sum3) {
36                    sum1 = maxSum1And2 + sum3;
37                    maxSubarraysIndices = new int[] {maxIndex1And2_1, maxIndex1And2_2, i - k + 1};
38                }
39              
40                // Subtract the oldest elements to maintain the size of k for the next iteration
41                sum1 -= nums[i - k * 3 + 1];
42                sum2 -= nums[i - k * 2 + 1];
43                sum3 -= nums[i - k + 1];
44            }
45        }
46      
47        // Return the indices of the three subarrays
48        return maxSubarraysIndices;
49    }
50}
51
1class Solution {
2public:
3    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
4        vector<int> answer(3); // This will store the starting indices of the three subarrays
5      
6        // Initialize sums of each subarray and maximum sum variables
7        int currentSum = 0, firstSubarraySum = 0, secondSubarraySum = 0, thirdSubarraySum = 0;
8        int maxFirstSubarraySum = 0, maxFirstSecondSum = 0;
9      
10        // Indices for tracking the maximum sums for subarrays
11        int maxFirstIndex = 0, maxFirstSecondIndex1 = 0, maxFirstSecondIndex2 = 0;
12      
13        // Loop through the array, starting from the end of the possible third subarray
14        for (int i = k * 2; i < nums.size(); ++i) {
15            // Increment the sum of each subarray with the next element in the sequence
16            firstSubarraySum += nums[i - k * 2];
17            secondSubarraySum += nums[i - k];
18            thirdSubarraySum += nums[i];
19          
20            // If we have completed the subarrays (reached full length of k for each)
21            if (i >= k * 3 - 1) {
22                // Update maximum sum and index for the first subarray if needed
23                if (firstSubarraySum > maxFirstSubarraySum) {
24                    maxFirstSubarraySum = firstSubarraySum;
25                    maxFirstIndex = i - k * 3 + 1;
26                }
27              
28                // Update the sum and indices for the first and second subarray
29                if (maxFirstSubarraySum + secondSubarraySum > maxFirstSecondSum) {
30                    maxFirstSecondSum = maxFirstSubarraySum + secondSubarraySum;
31                    maxFirstSecondIndex1 = maxFirstIndex;
32                    maxFirstSecondIndex2 = i - k * 2 + 1;
33                }
34              
35                // Update the total sum and starting indices for all three subarrays
36                if (maxFirstSecondSum + thirdSubarraySum > currentSum) {
37                    currentSum = maxFirstSecondSum + thirdSubarraySum;
38                    answer = {maxFirstSecondIndex1, maxFirstSecondIndex2, i - k + 1};
39                }
40              
41                // Move the window forward by subtracting the outgoing element from each subarray sum
42                firstSubarraySum -= nums[i - k * 3 + 1];
43                secondSubarraySum -= nums[i - k * 2 + 1];
44                thirdSubarraySum -= nums[i - k + 1];
45            }
46        }
47        return answer; // Return the starting indices of the subarrays
48    }
49};
50
1function maxSumOfThreeSubarrays(nums: number[], k: number): number[] {
2    let answer: number[] = new Array(3); // This will store the starting indices of the three subarrays
3
4    // Initialize sums of each subarray and maximum sum variables
5    let currentSum: number = 0, firstSubarraySum: number = 0;
6    let secondSubarraySum: number = 0, thirdSubarraySum: number = 0;
7    let maxFirstSubarraySum: number = 0, maxFirstSecondSum: number = 0;
8
9    // Indices for tracking the maximum sums for subarrays
10    let maxFirstIndex: number = 0, maxFirstSecondIndex1: number = 0;
11    let maxFirstSecondIndex2: number = 0;
12
13    // Loop through the array, starting from the end of the possible third subarray
14    for (let i: number = k * 2; i < nums.length; ++i) {
15        // Increment the sum of each subarray with the next element in the sequence
16        firstSubarraySum += nums[i - k * 2];
17        secondSubarraySum += nums[i - k];
18        thirdSubarraySum += nums[i];
19
20        // If we have completed the subarrays (reached full length of k for each)
21        if (i >= k * 3 - 1) {
22            // Update maximum sum and index for the first subarray if needed
23            if (firstSubarraySum > maxFirstSubarraySum) {
24                maxFirstSubarraySum = firstSubarraySum;
25                maxFirstIndex = i - k * 3 + 1;
26            }
27
28            // Update the sum and indices for the first and second subarray
29            if (maxFirstSubarraySum + secondSubarraySum > maxFirstSecondSum) {
30                maxFirstSecondSum = maxFirstSubarraySum + secondSubarraySum;
31                maxFirstSecondIndex1 = maxFirstIndex;
32                maxFirstSecondIndex2 = i - k * 2 + 1;
33            }
34
35            // Update the total sum and starting indices for all three subarrays
36            if (maxFirstSecondSum + thirdSubarraySum > currentSum) {
37                currentSum = maxFirstSecondSum + thirdSubarraySum;
38                answer = [maxFirstSecondIndex1, maxFirstSecondIndex2, i - k + 1];
39            }
40
41            // Move the window forward by subtracting the outgoing element from each subarray sum
42            firstSubarraySum -= nums[i - k * 3 + 1];
43            secondSubarraySum -= nums[i - k * 2 + 1];
44            thirdSubarraySum -= nums[i - k + 1];
45        }
46    }
47  
48    return answer; // Return the starting indices of the subarrays
49}
50

Time and Space Complexity

Time Complexity

The provided code has a main loop that runs from k * 2 to len(nums), where nums is the list of numbers, and k is the size of each subarray to be considered. The loop runs exactly len(nums) - k * 2 times. Inside the loop, only constant-time operations are performed, such as addition, subtraction, comparison, and assignment. Therefore, the time complexity of the algorithm mainly depends on the length of nums. The overall time complexity is O(n), where n is the length of the nums array.

Space Complexity

The space complexity considers the additional space required by the algorithm beyond the input data. In this case, the space complexity is O(1) since the algorithm uses a fixed number of variables (s, s1, s2, s3, mx1, mx12, idx1, idx12, ans) that do not grow with the input size. The array ans is returned as the result, but as it always contains only three elements (the starting indices of the three maximum subarrays), it does not scale with n.

Thus, the space usage is constant and does not depend on the size of the input array.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.


Recommended Readings

Got a question? Ask the Monster 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.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄