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).
首先用sliding window, 存下window下的sum.
然后類似于左右范圍內(nèi)的比較的問題葛菇，我們有一個left array和一個right array, 來存從左到右甘磨，left[i],到達i這個window的最大值。從右到左眯停，right[i],到達i這個window的最大值
然后重新掃描這些window, (表示第三個的位置)济舆，找到sum最大的地方。
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int sum = 0, len = nums.length - k + 1;
int[] sums = new int[len];
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (i >= k) sum -= nums[i - k];
if (i >= k - 1) sums[i - k + 1] = sum;
}
int[] left = new int[len];
int best = 0;
for (int i = 0; i < len; i++) {
if (sums[i] > sums[best]) best = i;
left[i] = best;
}
int[] right = new int[len];
best = len - 1;
for (int i = len - 1; i >= 0; i--) {
if (sums[i] >= sums[best]) best = i;
right[i] = best;
}
int[] res = {0, k, 2 * k};
for (int j = k; j < len - k; j++) {
int i = left[j - k], z = right[j + k];
if (sums[i] + sums[j] + sums[z] > sums[res[0]] + sums[res[1]] +
sums[res[2]]) {
res[0] = i;
res[1] = j;
res[2] = z;
}
}
return res;
}
}
