LWC 52：689. Maximum Sum of 3 Non-Overlapping Subarrays
LWC 52：689. Maximum Sum of 3 Non-Overlapping Subarrays
LWC 52：689. Maximum Sum of 3 Non-Overlapping Subarrays
传送门：689. Maximum Sum of 3 Non-Overlapping Subarrays
Problem:
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).
思路：
dp[i]：表示从i下标开始，长度为k的subArray的和。dp[i] = nums[i] + nums[i+1]+...+nums[i+k-1]，这样给定当前坐标i，只需要求出位于左侧的最大max{dp[i'] | i' <= i - k}记录之，同理求出右侧的最大max{dp[j] | j >= i + k}。
代码如下：
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int n = nums.length;
int[] sum = new int[n + 1];
// 累加和，区间计算时，只需O(1)
for (int i = 0; i < n; ++i) {
sum[i + 1] = nums[i] + sum[i];
}
int[] dp = new int[n];
// 对应最后一个区间的选择范围
for (int l = 2 * k; l + k <= n; ++l) {
dp[l] = sum[l + k] - sum[l];
}
// 对应第二个区间的选择范围
for (int l = k; l + 2 * k <= n; ++l) {
dp[l] = sum[l + k] - sum[l];
}
// 对应第一个区间的选择范围
for (int l = 0; l + 3 * k <= n; ++l) {
dp[l] = sum[l + k] - sum[l];
}
// 记录当前i下，符合i' <= i - k的dp[i']中最大下标
int[] left = new int[n];
for (int i = 0; i < n; ++i) {
if (i - k >= 0) {
if (left[i - 1] == -1) {
left[i] = i - k;
}
else if (dp[i - k] <= dp[left[i - 1]]) {
left[i] = left[i - 1];
}
else{
left[i] = i - k;
}
}
else {
left[i] = -1; //表示当前i的左侧没有合法的i'
}
}
// 记录当前i下，符合j >= i + k的dp[j]中最大下标
int[] right = new int[n];
for (int i = n - 1; i >= 0; --i) {
if (i + k < n) {
if (right[i + 1] == -1) {
right[i] = i + k;
}
else if (dp[right[i + 1]] > dp[i + k]) {
right[i] = right[i + 1];
}
else {
right[i] = i + k;
}
}
else {
right[i] = -1; //表示当前i的右侧没有合法的j
}
}
int max = 0;
int[] res = {-1, -1, -1};
for (int i = 0; i < n; ++i) {
if (left[i] != -1 && right[i] != -1) {
int tmp = dp[i] + dp[right[i]] + dp[left[i]];
if (tmp > max) {
max = dp[i] + dp[right[i]] + dp[left[i]];
res[0] = left[i];
res[1] = i;
res[2] = right[i];
}
}
}
return res;
}注意求解left和right中选取最大值的if判断，一个有等号，一个无等号，是为了 return the lexicographically smallest one.
精简版本：
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int n = nums.length;
int[] sum = new int[n + 1];
for (int i = 0; i < n; ++i) {
sum[i + 1] = nums[i] + sum[i];
}
int[] dp = new int[n];
for (int i = 0; i + k <= n; ++i){
dp[i] = sum[i + k] - sum[i];
}
int[] left = new int[n];
Arrays.fill(left, -1);
for (int i = k; i < n; ++i) {
if (i - k == 0 || dp[i - k] > dp[left[i - 1]]) {
left[i] = i - k;
}
else {
left[i] = left[i - 1];
}
}
int[] right = new int[n];
Arrays.fill(right, -1);
for (int i = n - k - 1; i >= 0; --i) {
if (i + k == n - 1 || dp[right[i + 1]] <= dp[i + k]){
right[i] = i + k;
}
else{
right[i] = right[i + 1];
}
}
int max = 0;
int[] res = {-1, -1, -1};
for (int i = 0; i < n; ++i) {
if (left[i] != -1 && right[i] != -1) {
int tmp = dp[i] + dp[right[i]] + dp[left[i]];
if (tmp > max) {
max = dp[i] + dp[right[i]] + dp[left[i]];
res[0] = left[i];
res[1] = i;
res[2] = right[i];
}
}
}
return res;
}