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

这道题使用动态规划

解法一：非常规的动态规划

这道题相当于选出3个长度为k的子数组，要求子数组和最大，返回的是每个子数组的第一个元素的下标。
首先，求所有长度为k的子数组的和，即sum，并将结果存储在对应首个元素索引下，例如，

输入：[1,2,1,2,6,7,5,1], 2
则：sum = {3,3,3,8,13,12,6}

如果nums数组长度为n，则sum数组长度为n-k+1
然后，思考找到3个长度为k的数组，并要求子数组和最大，在已经得到了sum的情况下，可以转化为求sum中3个原元素位置不重叠且3个sum元素值和最大。
这里假设选中sum[i]，那么只需要求其左右两边最大的sum值，但是注意其下标要不和i重叠，即至少小于等于i-k和大于等于i+k。

于是，设置两个数组left和right，left[i]表示从0到i的sum[i]最大值的下标，right[i]表示从n-1到i的sum[i]最大值的下标，注意这里的下标都是sum数组的下标而不是nums数组的。
于是3个选中的sum值的和就应该是
sum[left[i-k]] + sum[i] + sum[right[i+k]]

其中，以k = 2为例，sum[i]相当于nums[i], nums[i+1]，而sum[left[i-k]]相当于nums[i-2], nums[i-1]，sum[right[i+k]]相当于nums[i+2],nums[i+3]，这样就保证了元素的不重叠。

另外，这里求sum数组的时候，并没有使用N*N复杂度的计算，而是采用了首先设定一个初始值然后依次相加相减得到，复杂度降低。

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        vector<int> sum;
        int cnt = 0;
        for (int i = 0; i < k; ++i) {
            cnt += nums[i];
        }
        sum.push_back(cnt);
        for (int i = k; i < nums.size(); ++i) {
            cnt += nums[i] - nums[i - k];
            sum .push_back(cnt);
        }
        vector<int> ans(3);
        int n = sum.size();	// 注意是sum的长度
        vector<int> left(n, 0);
        vector<int> right(n, n - 1);
        for (int i = 1; i < n; ++i) {
            if(sum[i] > sum[left[i - 1]]) left[i] = i;
            else left[i] = left[i - 1];
        }
        for (int i = n - 2; i >= 0; --i) {
            if(sum[i] >= sum[right[i + 1]]) right[i] = i;
            else right[i] = right[i + 1];
        }
        int mx = 0;
        for (int i = k; i < n - k; ++i) {
            if (mx < sum[left[i - k]] + sum[i] + sum[right[i + k]]) {
                mx = sum[left[i - k]] + sum[i] + sum[right[i + k]];
                ans = {left[i - k], i, right[i + k]};
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

解法二：倒序动态规划

首先思考正常的动态规划的思路：
将i从0开始遍历，分别计算f(i)的值，而f(i)表示以索引值为i的元素为结尾的区间，得出的结果是索引值i更大的区间
在这道题中，我们设置f[i][j]表示以第i个元素为结尾的区间中包含j个不重叠子数组的和，分两种情况讨论：

1. 不包含Ai，则f[i][j] = f[i-1][j]
2. 包含Ai，相当于包含了[i-k, i]之间的元素区间，则f[i][j] = f[i-k][j-1] + (Si - Sk)，S表示前缀和

f[i][j]在其中取最大值。
上述过程有一种从右向左迭代的感觉

而由于题目里要求字典序从小到大，于是就要使用倒序DP
那么i就变为从末尾向前遍历，而f(i)也变成了以第i个元素为开头的区间，迭代从右向左变成了左向右，于是上述两种情况就变成了：

1. 不包含Ai，则f[i][j] = f[i+1][j]
2. 包含Ai，相当于包含了[i, i+k]之间的元素区间，则f[i][j] = f[i+k][j-1] + (Si+k - Si)，S表示前缀和

然后再确定好x，区间上届，遍历即可找到答案。

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        vector<int> ans;
        int n = nums.size();
        vector<int> s(n + 1);
        for (int i = 1; i < n + 1; ++i) {
            s[i] = s[i - 1] + nums[i - 1];
        }
        int x = n + 1;
        vector<vector<int>> f(n + 2, vector<int>(4));
        for (int i = n - k + 1; i > 0; --i) {
            for (int j = 1; j <= 3; ++j) {
                f[i][j] = max(f[i + 1][j], f[i + k][j - 1] + s[i + k - 1] - s[i - 1]);
                // 注意s的下标
            }
            if (f[x][3] <= f[i][3]) x = i;	// 这步是必须的，确定最小下标
        }
        int y = 3;
        while (y > 0) {
            while (f[x][y] != f[x + k][y - 1] + s[x + k - 1] - s[x - 1]) ++x;
            // 注意s的下标
            ans.push_back(x - 1);
            x += k;
            --y;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29