题目描述

给出非负整数数组 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。

样例

输入：A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2
输出：20
解释：子数组的一种选择中，[9] 长度为 1，[6,5] 长度为 2。

输入：A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2
输出：29
解释：子数组的一种选择中，[3,8,1] 长度为 3，[8,9] 长度为 2。

输入：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 >= 1
• M >= 1
• L + M <= A.length <= 1000
• 0 <= A[i] <= 1000

算法

(前缀后缀预处理) $O(n)$

1. 预处理前缀和数组 presum，后缀和数组 sufsum。
2. 用以上两个数组，预处理出前缀最大的 L 子数组的和 preL，前缀最大的 M 子数组的和 preM，后缀最大的 L 子数组的和 sufL，后缀最大的 M 子数组的和 sufM。
3. 根据两种情况 L 前 M 后或者 M 前 L 后分别统计最大值。

时间复杂度

• 遍历数组常数次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外预处理数组，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
        int n = A.size();
        vector<int> presum(n), sufsum(n);
        presum[0] = A[0];
        for (int i = 1; i < n; i++)
            presum[i] = presum[i - 1] + A[i];

        sufsum[n - 1] = A[n - 1];
        for (int i = n - 2; i >= 0; i--)
            sufsum[i] = sufsum[i + 1] + A[i];

        vector<int> preL(n, 0), preM(n, 0), sufL(n, 0), sufM(n, 0);
        preL[L - 1] = presum[L - 1];
        for (int i = L; i < n; i++)
            preL[i] = max(preL[i - 1], presum[i] - presum[i - L]);

        preM[M - 1] = presum[M - 1];
        for (int i = M; i < n; i++)
            preM[i] = max(preM[i - 1], presum[i] - presum[i - M]);

        sufL[n - L] = sufsum[n - L];
        for (int i = n - L - 1; i >= 0; i--)
            sufL[i] = max(sufL[i + 1], sufsum[i] - sufsum[i + L]);

        sufM[n - M] = sufsum[n - M];
        for (int i = n - M - 1; i >= 0; i--)
            sufM[i] = max(sufM[i + 1], sufsum[i] - sufsum[i + M]);

        int ans = 0;
        for (int i = L - 1; i < n - M; i++)
            ans = max(ans, preL[i] + sufM[i + 1]);        

        for (int i = M - 1; i < n - L; i++)
            ans = max(ans, preM[i] + sufL[i + 1]);

        return ans;
    }
};