输出最小字典序的DP

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 * 104
• 1 <= nums[i] < 216
• 1 <= k <= floor(nums.length / 3)

思路：
方法1：线性求解
求数组中最大值元素 -> 最大和次大值元素 -> …
求数组中定长区间和的最大值 -> 求数组中k个定长区间的最大值
都是一样的套路
方法2：DP + 前缀和
状态表示：f[i][j]表示考虑前i个元素中共有j个定长为k的区间的最大和
状态转移：考虑第i个元素，选或不选两种情况。
若选择第i个元素，f[i][j] = f[i - k][j - 1]
若不选第i个元素，f[i][j] = f[i - 1][j]
综上：f[i][j] = max(f[i - 1][j], f[i - k][j - 1])
考虑到本题需要输出选择的结果而不是最大值，并且是字典序最小的一个。
如果按照正常顺序从前往后DP，倒推的时候只能保证结果是最大的字典序，因为f[n - 1][3]只能由两个情况转移过来，f[n - 2][3]或者f[n - k - 1][2]。但该做法只能确保回溯出字典序最大的方案是正确（当两个可能的前驱节点都能转移到f[i][j] 时优先采纳靠后的位置）
所以需要换一下DP的方向，从后往前DP，这样从前往后寻找的方案就是字典序最小的。

//方法1：线性求解
class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int len) {
        int max1 = 0, idx1 = -1;
        int max2 = 0, idx21 = -1, idx22 = -1;
        int max3 = 0;
        int[] ans = new int[3];
        int s1 = 0, s2 = 0, s3 = 0;
        for (int i = 0, j = len, k = len * 2; k < nums.length; i++, j++, k++) {
            s1 += nums[i];
            s2 += nums[j];
            s3 += nums[k];
            if (s1 > max1) {
                max1 = s1;
                idx1 = i - len + 1;
            }
            if (max1 + s2 > max2) {
                max2 = max1 + s2;
                idx21 = idx1;
                idx22 = j - len + 1;
            }
            if (max2 + s3 > max3) {
                max3 = max2 + s3;
                ans[0] = idx21;
                ans[1] = idx22;
                ans[2] = k - len + 1;
            }
            if (i >= len - 1) {
                s1 -= nums[i - len + 1];
                s2 -= nums[j - len + 1];
                s3 -= nums[k - len + 1];
            }
        }
        return ans;
    }
}

//方法2：DP
class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] pre = new int[n + 1];
        for (int i = 1; i <= n; i++)
            pre[i] = pre[i - 1] + nums[i - 1];
        int[][] f = new int[n + 1][4];
        for (int i = n - k; i >= 0; i--) {
            for (int j = 1; j <= 3; j++) {
                f[i][j] = Math.max(f[i + 1][j], f[i + k][j - 1] + pre[i + k] - pre[i]);
            }
        }
        int y = 3;
        int idx = 0;
        int[] ans = new int[3];
        while (y > 0) {
            while (f[idx][y] != f[idx + k][y - 1] + pre[idx + k] - pre[idx])
                idx++;
            ans[3 - y] = idx;
            y--;
            idx += k;
        }
        return ans;
    }
}