689 Maximum Sum of 3 Non-Overlapping Subarrays

689. Maximum Sum of 3 Non-Overlapping Subarrays

1. Question

In a given arraynumsof positive integers, find three non-overlapping subarrays with maximum sum.

Each subarray will be of sizek, and we want to maximize the sum of all3*kentries.

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:

Input: [1,2,1,2,6,7,5,1], 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.

Note:

nums.lengthwill be between 1 and 20000.

nums[i]will be between 1 and 65535.k

will be between 1 and floor(nums.length / 3).

2. Implementation

(1) DP

思路:

1. 利用prefixSum数组，我们可以查到任意区间(i,j)的和，按照我们构造sum数组的方法，subarray(i,j)的和是sum[j + 1] - sum[i]

2. 我们可以利用leftIndex数组和rightIndex数组分别保存左边和右边最大subarray sum的起点，如果中间max sum subarray的区间是(i , i + k - 1), 那么左边数组的范围是(0, i - 1), 右边数组的范围(i + k, n - 1)

3. 注意当我们求最大右区间时，当前的subarray sum如果大于等于当前最大的subarray sum，我们为了让结果lexicographically small, 我们将其放入对应rightIndex数组里，这个处理和最大左区间不同

4. 中间区间的 i介于 (i, i + k - 1)之间，由于i + k - 1 <= n - k - 1 => i <= n - 2*k, 所以中间区间的起点在(k, n - 2 * k)

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] res = new int[3];

        if (nums == null || nums.length < 3 * k) {
            return res;
        }

        int n = nums.length;
        int[] sum = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }

        // the subarray sum between nums[i...j] will be sum[j + 1] - sum[i], i and j both starts with 0

        int[] leftIndex = new int[n];
        int[] rightIndex = new int[n];

        int curMaxSum = sum[k] - sum[0];

        // Find the start point of max left sum subarray
        // Since we have have calculated the sum of subarray(0, k - 1), we start at 1 here
        for (int i = 1; i <= n - k; i++) {
            if (sum[i + k] - sum[i] > curMaxSum) {
                leftIndex[i] = i;
                curMaxSum = sum[i + k] - sum[i];
            }
            else {
                leftIndex[i] = leftIndex[i - 1];
            }
        }

        curMaxSum = sum[n] - sum[n - k];
        rightIndex[n - k] = n - k;

        // Find the start point of max right sum subarray
        // Since we have have calculated the sum of subarray(n - k, n - 1), we start at n - k - 1 here
        for (int i = n - k - 1; i >= 0; i--) {
            // we use ">=" here because we try to make the answer lexicographically smaller.
            // i.e. when there are subarray sum equal to the curMaxSum, we try to make the start point 
            // as small as possible
            if (sum[i + k] - sum[i] >= curMaxSum) {
                rightIndex[i] = i;
                curMaxSum = sum[i + k] - sum[i];
            }
            else {
                rightIndex[i] = rightIndex[i + 1];
            }
        }

        // Find the start point of the max sum subarray in the middle
        int maxSum = Integer.MIN_VALUE;

        for (int i = k; i <= n - 2 * k; i++) {
            int leftStart = leftIndex[i - k], rightStart = rightIndex[i + k];

            curMaxSum = sum[leftStart + k] - sum[leftStart] + sum[rightStart + k] - sum[rightStart] + sum[i + k] - sum[i];

            if (curMaxSum > maxSum) {
                maxSum = curMaxSum;
                res[0] = leftStart;
                res[1] = i;
                res[2] = rightStart;
            }
        }
        return res;
    }
}

3. Time & Space Complexity

DP: 时间复杂度O(n), 空间复杂度O(n)