689 Maximum Sum of 3 Non-Overlapping Subarrays

689. Maximum Sum of 3 Non-Overlapping Subarrays

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

Each subarray will be of size k, and we want to maximize the sum of all 3*k entries.

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.length will be between 1 and 20000.

nums[i] will be between 1 and 65535.

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

--------------------------- 

算法：假设i为要求的第2个subarray的起始点，则在[0, i - 1]和[i + k, end]各存在一个subarray，找出这3个subaaray和的最大值时的坐标就可

恶心的实现题，注意各种index的计算，最好用一个具体例子。

计算subarray的题一般都要用到累加数组，这题也不例外。

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] rt = new int[3], sums = new int[n + 1], leftMax = new int[n], rightMax = new int[n];
        // 计算累加数组
        for (int i = 0; i < n; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }
        
        // 计算i左边的最大subarray和，DP
        for (int i = 1; i < n - 3 * k + 1; i++) {
            int cur = sums[i + k ] - sums[i];
            int preMax = sums[leftMax[i - 1] + k] - sums[leftMax[i - 1]];
            if (cur > preMax) {
                leftMax[i] = i;
            }else {
                leftMax[i] = leftMax[i - 1];
            }
        }

        // 计算i右边的最大subarray和，DP
        rightMax[n - k] = n - k;
        for (int i = n - k - 1; i >= 2 * k; i--) {
            int cur = sums[i + k] - sums[i];
            int preMax = sums[rightMax[i + 1] + k] - sums[rightMax[i + 1]];
            if (cur > preMax) {
                rightMax[i] = i;
            }else {
                rightMax[i] = rightMax[i + 1];
            }
        }

        int max = 0;
        for (int i = k; i <= n - 2 * k; i++) {
            int left = leftMax[i - k];
            int right = rightMax[i + k];
            int maxLeft = sums[left + k] - sums[left];
            int maxRight = sums[right + k] - sums[right];
            int cur = sums[i + k] - sums[i];
            int total = maxLeft + maxRight + cur;
            if (total > max) {
                rt[0] = left;
                rt[1] = i;
                rt[2] = right;
                max = total;
            }
        }

        return rt;
    }
}