689. Maximum Sum of 3 Non-Overlapping Subarrays - Detailed Explanation

Problem Statement

Description:
Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum total sum.
A subarray is a contiguous segment of the array. The three subarrays must not overlap.
Return the starting indices of these three subarrays that yield the maximum total sum. If multiple answers exist, return the lexicographically smallest one.

Examples:

1. Example 1:

   • Input: nums = [1,2,1,2,6,7,5,1], k = 2
   • Output: [0, 3, 5]
   • Explanation:
     The three subarrays are:
     • Subarray 1 (starting at index 0): [1,2] with sum = 3
     • Subarray 2 (starting at index 3): [2,6] with sum = 8
     • Subarray 3 (starting at index 5): [7,5] with sum = 12
       Total sum = 3 + 8 + 12 = 23, which is the maximum possible.

2. Example 2:

   • Input: nums = [1,2,1,2,1,2,1,2,1], k = 2
   • Output: [0,2,4]
   • Explanation:
     Although several valid combinations exist, the lexicographically smallest answer is returned.

Constraints:

• ( 1 \leq nums.length \leq 2 \times 10^4 )
• ( 1 \leq k \leq \lfloor \text{nums.length} / 3 \rfloor )
• The answer is guaranteed to exist.

Hints

• Hint 1:
  Think about precalculating the sum of every subarray of length k using a sliding window. This will allow you to quickly reference the sum of any subarray.

• Hint 2:
  To efficiently find the best left and right subarray candidates for any middle subarray, consider precomputing two arrays:

  • A left array where for every index i you store the starting index of the subarray with the maximum sum in the range ([0, i]).
  • A right array where for every index i you store the starting index of the subarray with the maximum sum in the range ([i, \text{end}]).

Approaches

Approach 1: Brute Force (Not Feasible)

Explanation

• Idea:
  Try every possible triple of non-overlapping subarrays and calculate their total sum.

• Steps:

  1. Iterate through all possible starting indices for the first subarray.
  2. For each, iterate for the second subarray ensuring it does not overlap.
  3. For each pair, iterate for the third subarray ensuring no overlap.
  4. Track the maximum total sum and the corresponding indices.

• Complexity:
  The time complexity would be O(n³) and is impractical for large inputs.

Approach 2: Sliding Window with Precomputation of Best Candidates

Explanation

This is the optimal and standard approach for this problem.

1. Compute Subarray Sums:

   • Use a sliding window to calculate the sum of every contiguous subarray of length k.
   • Store these sums in an array sum[] where sum[i] is the sum of the subarray starting at index i.

2. Precompute the Best Left Subarray for Each Position:

   • Create an array left[] where left[i] stores the starting index of the subarray (from 0 to i) that has the maximum sum.
   • Traverse the sum[] array from left to right, updating the best index as you go.

3. Precompute the Best Right Subarray for Each Position:

   • Create an array right[] where right[i] stores the starting index of the subarray (from i to end) that has the maximum sum.
   • Traverse the sum[] array from right to left.

4. Iterate for the Middle Subarray:

   • For each possible middle subarray (its starting index j should be between k and n - 2*k), combine:
     • The best left subarray ending before j (given by left[j-1]).
     • The middle subarray at index j.
     • The best right subarray starting after j+k-1 (given by right[j+k]).
   • Calculate the total sum and update the maximum if this combination yields a larger sum.
   • In case of ties, the lexicographically smallest indices are chosen by design of the left/right arrays.

Visual Walkthrough

Consider the array from Example 1:
nums = [1,2,1,2,6,7,5,1] with k = 2

1. Compute Subarray Sums:

   • Subarray starting at 0: [1,2] → sum = 3
   • Starting at 1: [2,1] → sum = 3
   • Starting at 2: [1,2] → sum = 3
   • Starting at 3: [2,6] → sum = 8
   • Starting at 4: [6,7] → sum = 13
   • Starting at 5: [7,5] → sum = 12
   • Starting at 6: [5,1] → sum = 6

2. Left Array Computation:

   • left[0] = 0
   • For index 1, best remains 0 (since 3 == 3, choose the earlier index).
   • For index 2, best remains 0.
   • For index 3, best becomes 3 (8 > 3).
   • For index 4, best becomes 4 (13 > 8).
   • And so on…

3. Right Array Computation:

   • right[6] = 6
   • For index 5, best becomes 5 (12 > 6).
   • For index 4, best remains 4 (13 > 12).
   • Continue updating from right to left.

4. Choose Middle Subarray:

   • Try every valid j for the middle subarray. For each, compute:
     total = sum[left[j-1]] + sum[j] + sum[right[j+k]]
   • Update the maximum total sum and store the indices.

Pseudocode

function maxSumOfThreeSubarrays(nums, k):
    n = length(nums)
    sum = array of size (n-k+1)
    window_sum = sum(nums[0:k])
    sum[0] = window_sum
    for i = 1 to n-k:
        window_sum = window_sum + nums[i+k-1] - nums[i-1]
        sum[i] = window_sum

    left = array of size length(sum)
    best = 0
    for i from 0 to length(sum)-1:
        if sum[i] > sum[best]:
            best = i
        left[i] = best

    right = array of size length(sum)
    best = length(sum)-1
    for i from length(sum)-1 down to 0:
        if sum[i] >= sum[best]:
            best = i
        right[i] = best

    max_total = 0
    answer = [-1, -1, -1]
    for j from k to length(sum)-k:
        i = left[j - k]    // best left subarray
        l = right[j + k]   // best right subarray
        total = sum[i] + sum[j] + sum[l]
        if total > max_total:
            max_total = total
            answer = [i, j, l]

    return answer

Code Examples

Python Code