1031.Maximum Sum of Two Non-Overlapping Subarrays

作者 Lucyyang 日期 2020-03-29
1031.Maximum Sum of Two Non-Overlapping Subarrays

一道比较有趣的求子序列和的题,LC1031,自己只相处了O(N^2)的做法,但实际上可以优化到O(N)的时间复杂度。

题目:给定一个非负的数组A,给定两个子串长度分别为L和M,找到A的不重叠的且和为最大的两个子串。

方法:类似于贪心的做法,现求出数组A的前缀和,然后我们先考虑位置i,i从L+M到A的末尾:第一种情况是数组M位置在[i-M, i],更新数组L在[i-M-L, i-M]时的最大值,MaxL=max(MaxL, preSum[i-M]-preSum[i-M-L]);第二种情况我们考虑数组L在[i-L,i]的位置上,更新此时的数组M在[i-M-L,i-L]的最大值,MaxM=max(MaxM, preSum[i-L]-preSum[i-L-L])。那么对于位置i,两个数组的最大和就在原来的结果,第一种的数组和,第二种的数组和这三种情况下进行选择。这样我们对每个能取到的右端点都进行了考虑,当i到A的末尾时,就为整个数组上的最大子序列和。

位置i示意图

代码:

class Solution {
public:
int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
if(A.size() < L+M)
return 0;
vector<int> preSum = A;
for(int i = 1; i < A.size(); i++) {
preSum[i] += preSum[i-1];
}
int res = preSum[L+M-1];
int maxL = preSum[L-1];
int maxM = preSum[M-1];
for(int i = L+M; i < A.size(); i++) {
maxL = max(maxL, preSum[i-M] - preSum[i-M-L]);
maxM = max(maxM, preSum[i-L]-preSum[i-M-L]);
res = max(res, max(maxL + preSum[i] - preSum[i-M], maxM + preSum[i] - preSum[i-L]));
}
return res;
}
};