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

本文主要是介绍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;}
};

解法二：倒序动态规划

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

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

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

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

不包含Ai，则f[i][j] = f[i+1][j]
包含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;}
};