689. 三个无重叠子数组的最大和 (opens new window)

1.枚举中点+前后缀和

常规三元问题思路枚举中心点，然后中心扩张取左右两侧最大值相加作为一次可能的最大和。用前后缀和维护两次子数组的最大和与起始坐标。

代码复杂度最终可以优化成一次遍历+空间O(1)。

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] padding = new int[nums.length - k+1];
        int sum=0;
        //统计所有大小为k的数组和
        for (int i = 0; i < nums.length; i++) {
            if(i<k) sum += nums[i];
            else{
                padding[i - k] = sum;
                sum += nums[i] - nums[i - k];
            }
            if(i==nums.length-1) padding[i - k + 1] = sum;
        }
        //维护后缀最大和，及其对应起始坐标
        int[][] maxTail = new int[padding.length][2];
        maxTail[padding.length - 1][0] = padding[padding.length - 1];
        maxTail[padding.length - 1][1] = padding.length - 1;
        for (int i = padding.length - 2; i >= 0; i--) {
            if (padding[i] >= maxTail[i + 1][0]) {
                maxTail[i][0] = padding[i];
                maxTail[i][1] = i;
            } else {
                maxTail[i][0] = maxTail[i + 1][0];
                maxTail[i][1] = maxTail[i + 1][1];
            }

        }
        //枚举中间位置的子数组，每次取前后最大子数组和相加作为一次可能的结果
        int maxHead = padding[0],head=0;
        int res = 0;
        int[] ans = new int[]{-1, -1, -1};
        for (int i = k; i < padding.length - k; i++) {
            if (padding[i - k] > maxHead) {
                maxHead = padding[i - k];
                head = i - k;
            }
            int tmpSum = maxHead + padding[i] + maxTail[i + k][0];
            if (tmpSum > res) {
                res = tmpSum;
                ans[0] = head;
                ans[1] = i;
                ans[2] = maxTail[i + k][1];
            }
        }
        return ans;
    }
}