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