问题:
给定一个数组,求从中取得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 };