class Solution {
public:
int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
}
};
1031. 两个非重叠子数组的最大和
给出非负整数数组 A ，返回两个非重叠（连续）子数组中元素的最大和，子数组的长度分别为 L 和 M。（这里需要澄清的是，长为 L 的子数组可以出现在长为 M 的子数组之前或之后。）
从形式上看，返回最大的 V，而 V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) 并满足下列条件之一：
0 <= i < i + L - 1 < j < j + M - 1 < A.length, 或0 <= j < j + M - 1 < i < i + L - 1 < A.length.
示例 1：
输入：A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2 输出：20 解释：子数组的一种选择中，[9] 长度为 1，[6,5] 长度为 2。
示例 2：
输入：A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2 输出：29 解释：子数组的一种选择中，[3,8,1] 长度为 3，[8,9] 长度为 2。
示例 3：
输入：A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3 输出：31 解释：子数组的一种选择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。
提示：
L >= 1M >= 1L + M <= A.length <= 10000 <= A[i] <= 1000原站题解
python3 解法, 执行用时: 44 ms, 内存消耗: 15.1 MB, 提交时间: 2022-12-05 16:13:17
class Solution:
def maxSumTwoNoOverlap(self, nums: List[int], L: int, M: int) -> int:
sums = [nums[0] for _ in range(len(nums))] # 前缀和数组 sums[i] = sum(nums[0..i])
for i in range(1, len(nums)):
sums[i] = sums[i-1] + nums[i]
# 非负整数数组的前缀和数组一定是递增的
res = sums[L + M -1] # 初始化为长度为 L + M 的最小连续子数组的和
Lmax = sums[L - 1] # 初始化为长度为 L 的最小连续子数组和
Mmax = sums[M - 1] # 初始化为长度为 M 的最小连续子数组和
# 以i的位置作为L数组或者M数组的右端
for i in range(L + M, len(sums)):
# 更新Lmax和Mmax
Lmax = max(Lmax, sums[i - M] - sums[i - M - L]) # Lmax与当前长度为L的子数组和比较，取大
Mmax = max(Mmax, sums[i - L] - sums[i - L - M]) # Mmax与当前长度为M的子数组和比较，取大
# L数组和M数组的相对位置有两种
LM = Lmax + sums[i] - sums[i - M] # L数组在M数组的左侧 L: [i-M-L .. i-M] M: [i-M .. i]
ML = Mmax + sums[i] - sums[i - L] # M数组在L数组的左侧 M: [i-L-M .. i-L] L: [i-L .. i]
res = max(res, max(LM, ML)) # 比较上一个结果和当前的两种选择
return res
cpp 解法, 执行用时: 0 ms, 内存消耗: 8.1 MB, 提交时间: 2022-12-05 16:11:58
class Solution {
public:
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;
}
};