LeetCode刷题【689】三个无重叠子数组的最大和

输入：nums = [1,2,1,2,6,7,5,1], k = 2
输出：[0,3,5]
解释：子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。
也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。

输入：nums = [1,2,1,2,1,2,1,2,1], k = 2
输出：[0,2,4]

动态规划【图解】

解题思路

1. 根据题面长度k区间，自然会想到的是滑动窗口来构建一个新的数组sumK
2. 接下来的思路稍微棘手点，但是如果你做过42. 接雨水，并且是用动态规划的方法来做的话，那么就会非常好理解了学了好久的动态规划再来做这题
3. 接雨水的思路是：找到左侧的最大值，同时找到右侧的最大值
4. 而这里，不能单纯的从左边右边移动一位，而是对应的需要移动距离k之外的最大值
5. 看图示例

1. 首先求得sumK数组 3 3 3 8 13 12 6
2. 接下来分别求左侧和右侧的最大值，下标0,1没有左侧区间，下标5,6也没有右侧区间
3. 左侧最大值从下标2开始，对应值为sumK[0]，之后往右移动，下标5的左侧最大值为sumK[3]，下标6同理
4. 右侧最大值为从右往左，原理同左侧最大值
5. 最终只遍历中间部分左右侧最大值都有的区间，找到和最大的那个值，并记下对应的下标索引

代码

class Solution {

    /*
    1,  2,  1,  2,  6,  7,  5,  1    k = 2
    3   3   3   8  13  12   6
            3   3   3   8  13
   13  13  13  12   6
     */


    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] sumK = new int[nums.length-k+1];
        for (int i = 0; i < k; i++) {
            sumK[0] += nums[i];
        }
        for (int i = 1; i < sumK.length; i++) {
            sumK[i] = sumK[i-1] + nums[i+k-1] - nums[i-1];
        }
//        System.out.println(Arrays.toString(sumK));
        int[][] dp = new int[sumK.length][2];
        boolean flag = false;
        for (int i = k; i < sumK.length - k; i++) {
            int j = sumK.length - i - 1;
            if (flag){
                dp[i][0] = sumK[i-k] > sumK[dp[i-1][0]] ? i-k : dp[i-1][0];
                dp[j][1] = sumK[j+k] >= sumK[dp[j+1][1]] ? j+k : dp[j+1][1];
            }else{
                flag = true;
                dp[i][0] = i-k;
                dp[j][1] = j+k;
            }
//            System.out.println(sumK[dp[i][0]] + "    "+sumK[dp[j][1]]);
        }
//        for (int[] ints : dp) {
//            System.out.println(Arrays.toString(ints));
//        }
        int[] res = new int[3];
        int max = 0;
        for (int i = k; i + k < sumK.length; i++) {
            int sum = sumK[i] + sumK[dp[i][0]] + sumK[dp[i][1]];
//            System.out.println("i  "+i + "  sum"+ sum);
            if ( sum > max){
                max = sum;
                res[0] = dp[i][0];
                res[1] = i;
                res[2] = dp[i][1];
            }
        }
        return res;
    }
}