689. Maximum Sum of 3 Non-Overlapping Subarrays

问题:

给定一个数组,求从中取得3组连续长度为 k 的子数组,使得3组数组和为最大,且使得3组的index尽可能小(★)。

Example:
Input: [1,2,1,2,6,7,5,1], 2
Output: [0, 3, 5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.
 

Note:
nums.length will be between 1 and 20000.
nums[i] will be between 1 and 65535.
k will be between 1 and floor(nums.length / 3).

  

解法:

动态规划:

要求3组子数组,则分别取得左最大,右最大,在遍历中间的所有可能,取得中间最大。

取得最大的方法:sum[nums[i] ~ nums[i+k]]=sum[i+k+1]-sum[i]

1. 因此,首先遍历nums,求得sum[i]=0~i-1的sum

注意:sum[0]=0,为了后续方便做减法,需要0. sum[1]=nums[0], sum[2]=nums[0]+nums[1],...

1 for(int i=1; i<=n; i++) sum[i]=nums[i-1]+sum[i-1];//0~n+1:{0,sum(0~0),sum(0~1)...}

2.由于最终以中间的子数组为判断对象,其首元素index范围在【k~n-2k】

解释【k~n-2k】:

极端情况:第一个数组取最开头【0~k-1】,那么中间的index最小可能取到 k

最后一个数组取最末尾【n-k~n-1】,那么中间的index最大取到n-k-1,其首元素index为n-k-1-(k-1)=n-2k

【0~k-1】【k~。。。~n-k-1】【n-k~n-1】

 

那么我们也只需要求的这个范围内的左边最大的各种情况,和右边最大的各种情况。

左边最大:

1         tmpmax=-1;
2         for(int i=k; i<=n-2*k; i++){
3             if(tmpmax<(sum[i]-sum[i-k])){
4                 tmpmax=sum[i]-sum[i-k];
5                 leftPos[i]=i-k;
6             }else{
7                 leftPos[i]=leftPos[i-1];
8             }
9         }

求得中间开始index为 i 时,左边最大情况下的左边数组首元素index

sum[nums[i-k] ~ nums[i-1]]=sum[i]-sum[i-k]

从左往右,如果出现更大的sum,那么到该 i 为止,左边最大的位置应被更新为更大sum的首元素index

若【小于等于】目前最大的sum,那么到该 i 为止,左边最大位置同前一个结果相同。

(由于要使index尽可能小(★),这里从左向右遍历,所以尽可能【不改变】已经取得的最大值)

 

右边最大:

1         tmpmax=-1;
2         for(int i=n-2*k; i>=k; i--){
3             if(tmpmax<=(sum[i+2*k]-sum[i+k])){
4                 tmpmax=sum[i+2*k]-sum[i+k];
5                 rightPos[i]=i+k;
6             }else{
7                 rightPos[i]=rightPos[i+1];
8             }
9         }

求得中间开始index为 i 时,右边最大情况下的右边数组首元素index

sum[nums[i+k] ~ nums[i+2*k-1]]=sum[i+2*k]-sum[i+k]

从右往左,如果出现更大的sum,那么到该 i 为止,右边最大的位置应被更新为更大sum的首元素index

若【小于】目前最大的sum,那么到该 i 为止,右边最大位置同前一个结果相同。

(由于要使index尽可能小(★),这里从右往左遍历,所以尽可能【改变】已经取得的最大值)

 

3.已有2求的到对应 i 为止,左边可得最大sum的index,和右边可得最大sum的index,

那么,再加上当前 i 的中间之和,为当前 i 的总最大sum

再遍历中间数组的所有可能:【k~n-2k】

取得当前最大:

 1         tmpmax=-1;
 2         for(int i=k; i<=n-2*k; i++){
 3             int l=leftPos[i];
 4             int r=rightPos[i];
 5             int tmpsum = (sum[i+k]-sum[i]) + (sum[l+k]-sum[l]) + (sum[r+k]-sum[r]);
 6             if(tmpsum>tmpmax){
 7                 res={l,i,r};
 8                 tmpmax=tmpsum;
 9             }
10         }

 最终得到的当前最大 res,则为所求。

 

代码参考:

 1 class Solution {
 2 public:
 3     vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
 4         int n=nums.size();
 5         int tmpmax=-1;
 6         vector<int>sum(n+1,0);
 7         vector<int>leftPos(n,0);
 8         vector<int>rightPos(n,0);
 9         vector<int>res(3,0);
10         for(int i=1; i<=n; i++) sum[i]=nums[i-1]+sum[i-1];//0~n+1:{0,sum(0~0),sum(0~1)...}
11         for(int i=k; i<=n-2*k; i++){
12             if(tmpmax<(sum[i]-sum[i-k])){
13                 tmpmax=sum[i]-sum[i-k];
14                 leftPos[i]=i-k;
15             }else{
16                 leftPos[i]=leftPos[i-1];
17             }
18         }
19         tmpmax=-1;
20         for(int i=n-2*k; i>=k; i--){
21             if(tmpmax<=(sum[i+2*k]-sum[i+k])){
22                 tmpmax=sum[i+2*k]-sum[i+k];
23                 rightPos[i]=i+k;
24             }else{
25                 rightPos[i]=rightPos[i+1];
26             }
27         }
28         tmpmax=-1;
29         for(int i=k; i<=n-2*k; i++){
30             int l=leftPos[i];
31             int r=rightPos[i];
32             int tmpsum = (sum[i+k]-sum[i]) + (sum[l+k]-sum[l]) + (sum[r+k]-sum[r]);
33             if(tmpsum>tmpmax){
34                 res={l,i,r};
35                 tmpmax=tmpsum;
36             }
37         }
38         return res;
39     }
40 };

 

上一篇:Day 1: subarray(maximum sum of contiguous subarray)


下一篇:寻找subarray sum的起止index