Problem
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]
Constraints:
1 <= nums.length <= 2 * 10^4
1 <= nums[i] < 216
1 <= k <= floor(nums.length / 3)
Solution
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int n = nums.length;
int[] sum = new int[n + 1];
int[] left = new int[n];
int[] right = new int[n];
int[] ret = new int[3];
// First get the prefix sum of nums.
// Prefix sum enables us to get the sum of k consecutive element in O(1) time
for (int i = 0; i < n; i++) {
sum[i + 1] = sum[i] + nums[i];
}
// DP for the left intetval max sum
for (int i = k, tot = sum[k] - sum[0]; i < n; i++) {
if (sum[i + 1] - sum[i - k + 1] > tot) {
tot = sum[i + 1] - sum[i - k + 1];
left[i] = i - k + 1;
} else {
left[i] = left[i - 1];
}
}
// DP for the right interval max sum
right[n - k] = n - k;
for (int i = n - 1 - k, tot = sum[n] - sum[n - k]; i >= 0; i--) {
if (sum[i + k] - sum[i] >= tot) {
tot = sum[i + k] - sum[i];
right[i] = i;
} else {
right[i] = right[i + 1];
}
}
// Find the max sum by iterating through the middle interval index based on above 2 cache.
int maxSum = 0;
for (int i = k; i <= n - 2 * k; i++) {
int l = left[i - 1], r = right[i + k];
int tot = sum[l + k] - sum[l] + sum[r + k] - sum[r] + sum[i + k] - sum[i];
if (tot > maxSum) {
ret[0] = l;
ret[1] = i;
ret[2] = r;
maxSum = tot;
}
}
return ret;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).