Code Implementation

class Solution:
    def maxSumOfThreeSubarrays(self, nums, k):
        n = len(nums)
        # Step 1: Compute sum of every subarray of size k
        sums = [0] * (n - k + 1)
        curr_sum = sum(nums[:k])
        sums[0] = curr_sum
        for i in range(1, n - k + 1):
            curr_sum += nums[i + k - 1] - nums[i - 1]
            sums[i] = curr_sum

        # Step 2: For each i, find the index of max sum subarray on the left (including i)
        left = [0] * len(sums)
        max_idx = 0
        for i in range(len(sums)):
            if sums[i] > sums[max_idx]:
                max_idx = i
            left[i] = max_idx

        # Step 3: For each i, find the index of max sum subarray on the right (including i)
        right = [0] * len(sums)
        max_idx = len(sums) - 1
        for i in range(len(sums) - 1, -1, -1):
            if sums[i] >= sums[max_idx]:
                max_idx = i
            right[i] = max_idx

        # Step 4: Try all middle intervals
        max_total = 0
        res = []
        for j in range(k, len(sums) - k):
            i = left[j - k]
            l = right[j + k]
            total = sums[i] + sums[j] + sums[l]
            if total > max_total:
                max_total = total
                res = [i, j, l]
        return res
      

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> sums(n - k + 1, 0);
        int curr_sum = 0;
        for (int i = 0; i < k; ++i) curr_sum += nums[i];
        sums[0] = curr_sum;
        for (int i = 1; i <= n - k; ++i) {
            curr_sum += nums[i + k - 1] - nums[i - 1];
            sums[i] = curr_sum;
        }
        vector<int> left(sums.size(), 0);
        int max_idx = 0;
        for (int i = 0; i < sums.size(); ++i) {
            if (sums[i] > sums[max_idx]) max_idx = i;
            left[i] = max_idx;
        }
        vector<int> right(sums.size(), 0);
        max_idx = sums.size() - 1;
        for (int i = sums.size() - 1; i >= 0; --i) {
            if (sums[i] >= sums[max_idx]) max_idx = i;
            right[i] = max_idx;
        }
        int max_total = 0;
        vector<int> res;
        for (int j = k; j < sums.size() - k; ++j) {
            int i = left[j - k];
            int l = right[j + k];
            int total = sums[i] + sums[j] + sums[l];
            if (total > max_total) {
                max_total = total;
                res = {i, j, l};
            }
        }
        return res;
    }
};
      

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] sums = new int[n - k + 1];
        int currSum = 0;
        for (int i = 0; i < k; i++) currSum += nums[i];
        sums[0] = currSum;
        for (int i = 1; i <= n - k; i++) {
            currSum += nums[i + k - 1] - nums[i - 1];
            sums[i] = currSum;
        }
        int[] left = new int[sums.length];
        int maxIdx = 0;
        for (int i = 0; i < sums.length; i++) {
            if (sums[i] > sums[maxIdx]) maxIdx = i;
            left[i] = maxIdx;
        }
        int[] right = new int[sums.length];
        maxIdx = sums.length - 1;
        for (int i = sums.length - 1; i >= 0; i--) {
            if (sums[i] >= sums[maxIdx]) maxIdx = i;
            right[i] = maxIdx;
        }
        int maxTotal = 0;
        int[] res = new int[3];
        for (int j = k; j < sums.length - k; j++) {
            int i = left[j - k];
            int l = right[j + k];
            int total = sums[i] + sums[j] + sums[l];
            if (total > maxTotal) {
                maxTotal = total;
                res[0] = i;
                res[1] = j;
                res[2] = l;
            }
        }
        return res;
    }
}
      

var maxSumOfThreeSubarrays = function(nums, k) {
    let n = nums.length;
    let sums = new Array(n - k + 1).fill(0);
    let currSum = 0;
    for (let i = 0; i < k; i++) currSum += nums[i];
    sums[0] = currSum;
    for (let i = 1; i <= n - k; i++) {
        currSum += nums[i + k - 1] - nums[i - 1];
        sums[i] = currSum;
    }
    let left = new Array(sums.length).fill(0);
    let maxIdx = 0;
    for (let i = 0; i < sums.length; i++) {
        if (sums[i] > sums[maxIdx]) maxIdx = i;
        left[i] = maxIdx;
    }
    let right = new Array(sums.length).fill(0);
    maxIdx = sums.length - 1;
    for (let i = sums.length - 1; i >= 0; i--) {
        if (sums[i] >= sums[maxIdx]) maxIdx = i;
        right[i] = maxIdx;
    }
    let maxTotal = 0;
    let res = [];
    for (let j = k; j < sums.length - k; j++) {
        let i = left[j - k];
        let l = right[j + k];
        let total = sums[i] + sums[j] + sums[l];
        if (total > maxTotal) {
            maxTotal = total;
            res = [i, j, l];
        }
    }
    return res;
};
      

Problem Description

You are given an integer array nums and an integer k. Your task is to find three non-overlapping subarrays of length k each, such that the sum of their elements is maximized. Return the starting indices of these three subarrays as an array of length 3.

• Each subarray must be of length k.
• The subarrays must not overlap, i.e., no element from nums is used in more than one subarray.
• There is exactly one solution (no need to handle ties).
• The answer should be the lexicographically smallest if multiple answers are possible (but the problem guarantees uniqueness).

Example:
Input: nums = [1,2,1,2,6,7,5,1], k = 2
Output: [0, 3, 5]

Thought Process

At first glance, this problem can be approached by brute force: try every possible combination of three non-overlapping subarrays of size k and calculate their sums. However, this approach quickly becomes infeasible for larger arrays, as the number of combinations grows rapidly.

To optimize, we notice that the structure of the problem allows us to precompute useful information. If we know, for every possible starting point, the best subarray to the left and right, we can efficiently find the best combination by fixing the middle subarray and looking up the optimal choices for the other two.

The main insight is to reduce redundant calculations by storing and reusing the maximum sum subarrays found so far, rather than recalculating them each time.

Solution Approach

We follow these steps to efficiently solve the problem:

1. Calculate all subarray sums of size k:
   • Use a sliding window to compute the sum of every contiguous subarray of length k in nums. Store these sums in an array sums.
2. Precompute the best left and right subarrays:
   • For each index in sums, store the index of the subarray with the maximum sum to the left (including itself) in an array left.
   • Similarly, for each index, store the index of the subarray with the maximum sum to the right (including itself) in an array right.
3. Iterate over possible middle subarrays:
   • For each possible starting index j of the middle subarray (from k to len(sums) - k - 1), use left[j-k] for the best left subarray and right[j+k] for the best right subarray.
   • Calculate the total sum and update the result if a new maximum is found.
4. Return the result:
   • The indices of the three subarrays that give the maximum total sum.

This approach ensures that every possible valid combination is considered, but only in linear time.

Example Walkthrough

Let's use the example nums = [1,2,1,2,6,7,5,1] and k = 2.

1. Compute all subarray sums of size 2:
   The subarrays and their sums:
   • [1,2] = 3 (index 0)
   • [2,1] = 3 (index 1)
   • [1,2] = 3 (index 2)
   • [2,6] = 8 (index 3)
   • [6,7] = 13 (index 4)
   • [7,5] = 12 (index 5)
   • [5,1] = 6 (index 6)
   So, sums = [3,3,3,8,13,12,6]
2. Precompute left max indices:
   • left[0]=0, left[1]=0, left[2]=0, left[3]=3, left[4]=4, left[5]=4, left[6]=4
3. Precompute right max indices:
   • right[6]=6, right[5]=5, right[4]=4, right[3]=4, right[2]=4, right[1]=4, right[0]=4
4. Try each possible middle subarray (j from 2 to 4):
   • For j=2: left=0, right=4 → sums: 3+3+13=19
   • For j=3: left=0, right=5 → sums: 3+8+12=23
   • For j=4: left=0, right=6 → sums: 3+13+6=22
   The maximum is 23 at indices [0,3,5].
5. Return [0, 3, 5]

This step-by-step process ensures we find the optimal non-overlapping subarrays.

Time and Space Complexity

• Brute-force approach:
  • Time complexity: O(n³), since you would check all possible triplets of subarrays.
  • Space complexity: O(1), if not storing intermediate results.
• Optimized approach (as described above):
  • Time complexity: O(n), where n is the length of nums. Each step (sums, left, right, final loop) is linear.
  • Space complexity: O(n), for storing sums, left, and right arrays.

The dramatic improvement comes from using precomputed arrays to avoid redundant calculations.

Summary

The key to solving the "Maximum Sum of 3 Non-Overlapping Subarrays" problem is recognizing overlapping subproblems and using precomputed arrays to efficiently find the best left and right subarrays for any middle subarray. By leveraging sliding window sums and dynamic programming ideas, we reduce the complexity from cubic to linear, making the solution practical for large inputs. This method elegantly balances clarity and efficiency, and is a great example of how careful precomputation can transform a brute-force problem into an optimal one.