LeetCode 689. Maximum Sum of 3 Non-Overlapping Subarrays

题目：给定一个数组nums，给定一个整数k，求数组内k长度的子串和最大的3个子串位置。（位置不可重复，结果数字序要求最小）

比如：

Input: [1,2,1,2,6,7,5,1], 2
Output: [0, 3, 5]

最大为 [1, 2] [2, 6] [7, 5]的和

思路：看到带3的题目，首先要想到利用3。3代表着可以构成左中右结构，也就是说只要能知道当前位置符合要求的左边最大值，右边最大值就知道了答案。

那么第一步就是先求出子串和的数组（打印输出以上面例子作为输入）：

let sumArray = [];
let sum = 0;
for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    if (i >= k) sum -= nums[i - k];
    if (i >= k - 1) sumArray[i - k + 1] = sum;
}
console.log(sumArray); // [ 3, 3, 3, 8, 13, 12, 6 ]

然后相应的求出当前i位置的左侧最大值，和右侧最大值：

let left = [];
left[0] = 0;
for (let i = 1; i < sumArray.length; i++) {
    left[i] = sumArray[left[i-1]] >= sumArray[i] ? left[i-1] : i;
}
console.log(left); // [ 0, 0, 0, 3, 4, 4, 4 ]

let right = [];
right[sumArray.length - 1] = sumArray.length - 1;
for (let i = sumArray.length - 2; i >= 0; i--) {
    right[i] = sumArray[right[i+1]] >= sumArray[i] ? right[i+1] : i;
}
console.log(right); // [ 4, 4, 4, 4, 4, 5, 6 ]

最后，循环数组，计算出最大值和所在位置就可以了，完整代码如下：

var maxSumOfThreeSubarrays = function(nums, k) {
    let result = [];
    let sumArray = [];
    let sum = 0;
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (i >= k) sum -= nums[i - k];
        if (i >= k - 1) sumArray[i - k + 1] = sum;
    }
    console.log(sumArray);

    let left = [];
    left[0] = 0;
    for (let i = 1; i < sumArray.length; i++) {
        left[i] = sumArray[left[i-1]] >= sumArray[i] ? left[i-1] : i;
    }
    console.log(left);

    let right = [];
    right[sumArray.length - 1] = sumArray.length - 1;
    for (let i = sumArray.length - 2; i >= 0; i--) {
        right[i] = sumArray[right[i+1]] >= sumArray[i] ? right[i+1] : i;
    }
    console.log(right);
    
    let ans = [0, k, 2 * k];
    for (let i = k; i < sumArray.length - k; i++) {
        if (sumArray[i] + sumArray[left[i - k]] + sumArray[right[i + k]] > sumArray[ans[0]] + sumArray[ans[1]] + sumArray[ans[2]]) {
            ans = [left[i - k], i, right[i+k]]
        }
    }
    console.log(ans);
    
    return ans;
};