689.三个无重叠子数组的最大和

//给你一个整数数组 nums 和一个整数 k ，找出三个长度为 k 、互不重叠、且 3 * k 项的和最大的子数组，并返回这三个子数组。 
//
// 以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置（下标从 0 开始）。如果有多个结果，返回字典序最小的一个。 
//
// 
//
// 示例 1： 
//
// 
//输入：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] 在字典序上更大。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,1,2,1,2,1,2,1], k = 2
//输出：[0,2,4]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 2 * 10⁴ 
// 1 <= nums[i] < 2¹⁶ 
// 1 <= k <= floor(nums.length / 3) 
// 
// Related Topics 数组 动态规划 👍 282 👎 0

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] baba = new int[3];
        int sum1 = 0, sum2 = 0, sum3 = 0;
        int max1 = 0, max2 = 0, max3 = 0;
        int maxIndex = 0, maxIndex1=0, maxIndex2 = 0;
        for(int i = 2*k;i<nums.length;i++){
            sum1 += nums[i-2*k];
            sum2 += nums[i-k];
            sum3 += nums[i];
            //当窗口的末端到底边界时
            //判断前两个窗口是否满足最大的条件
            if(i>=3*k-1){
                if(sum1 > max1){
                    //第一个窗口的最大值
                    max1 = sum1;
                    maxIndex = i-3*k+1;
                }
                if(max1 + sum2 > max2){
                    max2 = max1 + sum2;
                    maxIndex1 = maxIndex;
                    //第二个窗口的最大值
                    maxIndex2=i-2*k+1;
                }
                if(max2 + sum3 > max3){
                    max3 = max2 + sum3;
                    baba[0] = maxIndex1;
                    baba[1] = maxIndex2;
                    baba[2] = i-k+1;
                }
                sum1 -= nums[i-3*k+1];
                sum2 -= nums[i-2*k+1];
                sum3 -= nums[i-k+1];
            }
        }
        return baba;
    }
}