LeetCode 1031 两个非重叠子数组的最大和
🟡 中等 https://leetcode.cn/problems/maximum-sum-of-two-non-overlapping-subarrays/description/
思路
一个容易理解的解法：
这个思路先从“两数和最大值”类比出发：右侧枚举右端点，同时维护左侧历史最大值 left_max，每次更新 res = max(res, nums[i] + left_max)。本题只是把“一个数”替换成“一个固定长度子数组”。
记录前缀和可以求任意长度的子数组和。
这题下标细节较多，写代码时要格外注意边界。
class Solution {
public:
int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
vector<int> pre_sum(nums.size()+1,0);
for(int i = 0;i<=nums.size()-1;i++){
pre_sum[i+1] = pre_sum[i]+nums[i];//包含nums[i]->pre_sum[i+1]
}
int res = 0;
int max_left_all = 0;
//遍历次数 为secondLen+1
for(int i = 0+firstLen-1;i<=nums.size()-1-(secondLen+1)+1;i++){
max_left_all = max(max_left_all,pre_sum[i+1]-pre_sum[i-(firstLen+1)+1+1]);
res = max(res,max_left_all+pre_sum[i+(secondLen+1)-1+1]-pre_sum[i+1]);
}
int max_left_all_sec = 0;
for(int i = 0+secondLen-1;i<=nums.size()-1-(firstLen+1)+1;i++){
max_left_all_sec = max(max_left_all_sec,pre_sum[i+1]-pre_sum[i-(secondLen+1)+1+1]);
res = max(res,max_left_all_sec+pre_sum[i+(firstLen+1)-1+1]-pre_sum[i+1]);
}
return res;
}
};
也可以把 for 循环抽成函数：
class Solution {
public:
int get(int left,int right,int nums_size,vector<int>& pre_sum){
int res = 0;
int max_left_all = 0;
//遍历次数 为secondLen+1
for(int i = 0+left-1;i<=nums_size-1-(right+1)+1;i++){
max_left_all = max(max_left_all,pre_sum[i+1]-pre_sum[i-(left+1)+1+1]);
res = max(res,max_left_all+pre_sum[i+(right+1)-1+1]-pre_sum[i+1]);
}
return res;
}
int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
vector<int> pre_sum(nums.size()+1,0);
for(int i = 0;i<=nums.size()-1;i++){
pre_sum[i+1] = pre_sum[i]+nums[i];//包含nums[i]->pre_sum[i+1]
}
return max(get(firstLen,secondLen,nums.size(),pre_sum),get(secondLen,firstLen,nums.size(),pre_sum));
}
};
也可以一遍过：从 L + M 开始遍历，同时讨论 LM 和 ML 两种顺序。
int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
for (int i = 1; i < A.size(); ++i)
A[i] += A[i - 1];
int res = A[L + M - 1], Lmax = A[L - 1], Mmax = A[M - 1];
for (int i = L + M; i < A.size(); ++i) {
Lmax = max(Lmax, A[i - M] - A[i - L - M]);
Mmax = max(Mmax, A[i - L] - A[i - L - M]);
res = max(res, max(Lmax + A[i] - A[i - M], Mmax + A[i] - A[i - L]));
}
return res;
}