689. Maximum Sum Of 3 Non Overlapping Subarrays¶

Difficulty: Hard

689. Maximum Sum of 3 Non-Overlapping Subarrays

Hard

Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example 1:

Input: nums = [1,2,1,2,6,7,5,1], k = 2
Output: [0,3,5]
Explanation: 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.

Example 2:

Input: nums = [1,2,1,2,1,2,1,2,1], k = 2
Output: [0,2,4]

Constraints:

1 <= nums.length <= 2 * 10⁴
1 <= nums[i] < 2¹⁶
1 <= k <= floor(nums.length / 3)

Solution¶

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] sums = new int[n - k + 1];
        int windowSum = 0;
        for (int i = 0; i < n; i++) {
            windowSum += nums[i];
            if (i >= k - 1) {
                sums[i - k + 1] = windowSum;
                windowSum -= nums[i - k + 1];
            }
        }
        int[] left = new int[sums.length];
        int leftMaxIndex = 0;
        for (int i = 0; i < sums.length; i++) {
            if (sums[i] > sums[leftMaxIndex]) {
                leftMaxIndex = i;
            }
            left[i] = leftMaxIndex;
        }

        int[] right = new int[sums.length];
        int rightMaxIndex = sums.length - 1;
        for (int i = sums.length - 1; i >= 0; i--) {
            if (sums[i] >= sums[rightMaxIndex]) {
                rightMaxIndex = i;
            }
            right[i] = rightMaxIndex;
        }

        int maxSum = 0;
        int[] result = new int[3];
        for (int mid = k; mid < sums.length - k; mid++) {
            int l = left[mid - k], r = right[mid + k];
            int totalSum = sums[l] + sums[mid] + sums[r];
            if (totalSum > maxSum) {
                maxSum = totalSum;
                result = new int[] {l, mid, r};
            }
        }
        return result;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here