Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.
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 1:
**Input:** nums = [1,2,1,2,6,7,5,1], k = 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.
Example 2:
**Input:** nums = [1,2,1,2,1,2,1,2,1], k = 2
**Output:** [0,2,4]
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
// edge cases
if (nums == null || nums.length == 0 || nums.length < 3 * k) {
return new int[0];
}
// get subarray sum
int[] subsum = new int[nums.length - k + 1];
for (int i = 0; i < k; i++) {
subsum[0] += nums[i];
}
for (int i = 1; i < subsum.length; i++) {
subsum[i] = subsum[i-1] - nums[i-1] + nums[i+k-1];
}
// dp, left[i], right[i]
int[] left = new int[subsum.length]; // maximum to the left
int[] right = new int[subsum.length]; // maximun to the right
int max = 0;
for (int i = 0; i < left.length; i++) {
int i2 = i - k;
if (i2 < 0) {
left[i] = -1;
continue;
}
if (subsum[i2] > subsum[max]) max = i2; // update max value and index
left[i] = max;
}
max = subsum.length - 1;
for (int i = subsum.length - 1; i >= 0; i--) {
int i2 = i + k;
if (i2 >= subsum.length) {
right[i] = -1;
continue;
}
if (subsum[i2] >= subsum[max]) max = i2;
right[i] = max;
}
// get result
long maxSum = Long.MIN_VALUE;
int[] res = new int[3];
for (int i = 0; i < subsum.length; i++) {
if (left[i] == -1 || right[i] == -1) continue;
long tmpSum = subsum[left[i]] + subsum[i] + subsum[right[i]];
if (tmpSum > maxSum) { // update max
maxSum = tmpSum;
res[0] = left[i];
res[1] = i;
res[2] = right[i];
}
}
return res;
}
}
ac2:
Don't even understand by looking at it. Impossible to figure out in the interview.
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int[] res = new int[3];
// edge cases
if (nums == null || nums.length == 0 || k <= 0 || nums.length / k < 3) return res;
int n = nums.length;
int xSubarrays = 3; // x means how many subarrays
int[][] max = new int[xSubarrays+1][n+1];
int[][] idx = new int[xSubarrays+1][n+1];
int[] sum = new int[n+1];
// init accumulation sum, in order to get subarray sum
for (int i = 1; i < sum.length; i++) sum[i] = sum[i-1] + nums[i-1];
// iterate
for (int x = 1; x <= xSubarrays; x++) {
for (int i = x * k; i < max[0].length; i++) {
int tmp = max[x-1][i-k] + (sum[i] - sum[i-k]);
if (tmp > max[x][i-1]) { // find greater sum, update info
max[x][i] = tmp;
idx[x][i] = i - k;
} else {
max[x][i] = max[x][i-1];
idx[x][i] = idx[x][i-1];
}
}
}
// get indices
res = new int[xSubarrays];
res[xSubarrays-1] = idx[xSubarrays][n];
for (int i = xSubarrays - 2; i >= 0; i--) {
int prevIdx = res[i+1];
res[i] = idx[i+1][prevIdx];
}
return res;
}
}
/*
so hard to understand the indices, a better approach is to have an example
*/