In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum.
Each subarray will be of size k, and we want to maximize the sum of all 3*k entries.
Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.
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).
思路：
We need to find 3 subarrays
Let's say if I can find the 2nd subarray , then find the largest subarray on both left side and right side, problem solved.
代码：
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int[] sum = new int[nums.length]; // sum[i] = num[i] + nums[i+1]...+nums[i+k-1];
int[] lef = new int[nums.length]; // lef[i] = before i, the max sum[];
int[] rig = new int[nums.length]; // rif[i] = after i, the max sum[];
int[] IndexL = new int[nums.length];
int[] IndexR = new int[nums.length];
int total = 0;
//build sum[]
for(int i=0; i<nums.length; i++){
if(i <= k-1){
total += nums[i];
}else{
total = total + nums[i] - nums[i-k];
}
if(i-k+1>=0){
sum[i-k+1] = total;
}
}
int max = 0;
//build lef[]
for(int i=0; i<=nums.length-k; i++){ //i-k+1 < nums.length -> j < n-k+1
if(sum[i] > max){
max = sum[i];
lef[i] = max;
IndexL[i] = i;
}else{
lef[i] = lef[i-1];
IndexL[i] = IndexL[i-1];
}
}
max = 0;
//build rig[]
for(int i=nums.length-k; i>=0; i--){
if(sum[i] >= max){
max = sum[i];
rig[i] = max;
IndexR[i] = i;
}else{
rig[i] = rig[i+1];
IndexR[i] = IndexR[i+1];
}
}
// find 2rd subarray;
total = 0;
int ret = 0;
int[] ans = new int[3];
for(int i=k; i<=nums.length-2*k; i++){ // since no overlap so start with k;
total = sum[i] + lef[i-k] + rig[i+k]; //i+k <= nums.length-k
if(total > ret){
ret = total;
total = 0;
ans[0] = IndexL[i-k];
ans[1] = i;
ans[2] = IndexR[i+k];
}
}
return ans;
}
}
