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

方法一：动态规划 + 前缀和

首先按照正序进行动态规划，定义 f[i][j] 为考虑前 i 个数，凑成无重叠子数组数量为 j 个时的最大值。

dp[i][j] 的计算分两种情况来讨论

• 最优方案包含 nums[i]，即 i 位置作为当前区间的最后一个位置，这时计算公式为：

$$ f[i][j]=f[i−k][j−1]+ \sum_{idx=i-k+1}^inums[idx] $$

后面这部分就是前缀和

• 最优方案不包含 nums[i]，此使有

$$ f[i][j] = f[i - 1][j] $$

得到f数组所有的结果后，f[n-1][3] 就是最大值的结果，要判断它由 f[n - 2][3] 转移来的还是由 $$ f[n - 1 - k][2]+ \sum_{idx=i-k+1}^inums[idx] $$ 转移来的，确定之后就能确定最后一个区间的最后一个位置。确定之后用相同的方式就能确定上一个区间源自哪里。

这样的方法固然好，但是这样做只能保证这几个区间一定是3个无重叠子数组的和最大，但是无法保证这就是字典序的区间，所以要进行倒序操作。

在正序操作中是把 i 位置区间的最后一个位置，但是在倒序操作中是把 i 位置作为区间的第一个位置来看。

f[i][j] 的含义也发生了变化，即考虑[i .... n - 1]个数，无重叠子数组数正好为 j 个时的最大值。这样在计算完 f 数组后，就从左往右扫，找到的肯定是字典序最小的情况。

注意：

• dp 数组和 sum 数组都是相比于原数组后移了一位
• 区间的下标位置关系： [i, i + k - 1] 和 [i - k + 1, i]

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] sum = new int[n + 1]; // 前缀和数组
        long[][] dp = new long[n + 10][4];
        int[] ans = new int[3]; // 结果数组
        // 计算前缀和，相比于nums数组每个位置后移一位
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
        // n - k + 1怎么计算出来的呢？根据[i - k + 1, i]，i最大为n-1，则i-k+1则为n-k
        // 又因为dp数组相比于nums数组右移一位，所以为n-k+1
        for (int i = n - k + 1; i >= 1; i--) {
            for (int j = 1; j < 4; j++) {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i + k][j - 1] + sum[i + k - 1] - sum[i - 1]);
            }
        }
        int idx = 0, i = 1, j = 3;
        // 按照定义来讲，应该找dp[0][3]即[0,n-1]数组内凑够3个无重叠数组的最大值，因为相对右移1位
        // 所以ic
        while (j > 0) {
            if (dp[i + 1][j] > dp[i + k][j - 1] + sum[i + k - 1] - sum[i - 1]) {
                i++;
            } else {
                ans[idx++] = i - 1;
                i += k;
                j--;
            }
        }
        return ans;
    }
}