[Leetcode]689.Maximum Sum of 3 Non-Overlapping Subarrays

追风赶月莫停留，平芜尽处是春山。这篇文章主要讲述[Leetcode]689.Maximum Sum of 3 Non-Overlapping Subarrays相关的知识，希望能为你提供帮助。
【[Leetcode]689.Maximum Sum of 3 Non-Overlapping Subarrays】链接：LeetCode689
给定数组 nums 由正整数组成，找到三个互不重叠的子数组的最大和。
每个子数组的长度为k，我们要使这3*k个项的和最大化。
返回每个区间起始索引的列表（索引从 0 开始）。如果有多个结果，返回字典序最小的一个。
示例:
输入: \$[1,2,1,2,6,7,5,1], 2\$
输出: \$[0, 3, 5]\$
解释: 子数组 \$[1, 2], [2, 6], [7, 5]\$ 对应的起始索引为 \$[0, 3, 5]\$。
我们也可以取 \$[2, 1]\$, 但是结果 \$[1, 3, 5]\$ 在字典序上更大。
相关标签：动态规划
又是一道明确是用动态规划解法后，便不难想出动态转移方程的题目。
下面考虑一般情况，也就是求解划分成\$N\$个不重叠数组的最大和。
假设到第\$i\$个元素为止，一共已经产生了\$j\$个不重叠数组，那么令$ dp[i][j] \$表示这\$j\$个不重叠数组的最大和。然后就要寻找状态转移方程。**对于第\$i$个元素，分为两种情况，可取可不取。**
如果取，那就说明 \$nums[i]\$ 是第\$j\$个子数组的最后一个元素，那么转移方程为：

\\[dp[i][j] = dp[i-k][j-1]+nums_{i-k+1:i} \\]
也就是说，从\$i-k+1\$到\$i\$，这\$k\$个元素构成了第\$j\$个子数组，那我们只需要求到第\$i-k\$个元素为止，产生\$j-1\$个不重叠数组的最大和即可。
如果不取，那问题就变成了求到第\$i-1\$个元素为止，产生\$j\$个不重叠数组的最大和，那么转移方程为：

\\[dp[i][j] = dp[i-1][j] \\]
当然这题的难度还在于，需要你还原出最大和的情况下，所有子数组的起始元素下标，所以需要另外用一个数组保存一下每一步的最优下标。
同样，假设到第\$i\$个元素为止，一共已经产生了\$j\$个不重叠数组，用\$path[i][j]\$表示第\$j\$个子数组的末尾元素下标。
那么按照上面的推断，如果取第\$i\$个元素，那么\$path[i][j]=i\$；否则的话 \$path[i][j]=path[i-1][j]\$。最后就是根据 path 数组还原答案了。
其代码如下：
python:

class Solution: def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]: n = len(nums) dp = [[0 for j in range(4)] for i in range(n+1)] path = [[0 for j in range(4)] for i in range(n+1)] cur = sum(nums[:k]) sums = [cur] for i in range(k,n): cur += nums[i] - nums[i-k] sums.append(cur)for i in range(1,n+1): for j in range(1,4): if i < j*k: dp[i][j] = 0 continue dp[i][j] = dp[i-1][j] path[i][j] = path[i-1][j] if dp[i-k][j-1] + sums[i-k] > dp[i][j]: dp[i][j] = dp[i-k][j-1] + sums[i-k] path[i][j] = i-kres = [] ind = n for j in reversed(range(1,4)): res.append(path[ind][j]) ind = path[ind][j] res.reverse() return res

C++:

class Solution { public: vector< int> maxSumOfThreeSubarrays(vector< int> & nums, int k) { int n = nums.size(); vector< vector< int> > dp(n+1,vector< int> (4,0)); vector< vector< int> > path(n+1,vector< int> (4,0)); int cur = accumulate(nums.begin(),nums.begin()+k,0); vector< int> sums{cur}; for(int i=k; i< n; ++i){ cur += nums[i]-nums[i-k]; sums.push_back(cur); } for(int i=1; i< n+1; ++i){ for(int j=1; j< 4; ++j){ if(i< j*k){ continue; } dp[i][j] = dp[i-1][j]; path[i][j] = path[i-1][j]; if(dp[i-k][j-1]+sums[i-k]> dp[i][j]){ dp[i][j] = dp[i-k][j-1]+sums[i-k]; path[i][j] = i-k; } } } vector< int> res; int ind = n; for (int j=3; j> 0; --j){ res.insert(res.begin(),path[ind][j]); ind = path[ind][j]; } return res; } };

参考：[LeetCode 689]三个无重叠子数组的最大和