博客

思路

1. 计算前缀和
2. 滑动窗口，不使用存储空间，使用擂台法
3. 模拟L在M前，或M在L前，取最大值

例子

0 6 5 2 2 5 1 9 4 L=1 M=2

那么以L为滑动窗口 依次得到 <0> <6> <5> <2> <2> <5>...
模拟L在M前,M为 <6,5> <5,2> <2,2>...

以M为滑动窗口 依次得到<0,6> <6,5> <5,2> <2,2>...
模拟M在L前，L为 <5> <2> <2> <5>...

maxL=0
maxM=6
res=max(6,0+6+5,6+5)=11

maxL=6
maxM=11
res=max(11,6+5+2,11+2)=13

maxL=6
maxM=11
res=max(13,6+2+2,11+2)=13
...


思考：
1. 代码中如何避免了重复元素？
2. 代码中如何保证答案的覆盖率？

代码

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]+A[i];
        
        int maxsum = A[L+M-1], maxsumL = A[L-1], maxsumM = A[M-1];
        for(int i = L+M; i < A.size(); ++i){
            //保存最大的L
            maxsumL = max(maxsumL, A[i-M]-A[i-M-L]);
            //保存最大的M
            maxsumM = max(maxsumM, A[i-L]-A[i-L-M]);
            //模拟L在M前  M在L前
            maxsum = max(maxsum, 
                            max(maxsumL+A[i]-A[i-M], 
                                maxsumM+A[i]-A[i-L]));
        }
        return maxsum;
    }
};