1031. 两个非重叠子数组的最大和

题目链接：1031. 两个非重叠子数组的最大和

方法：前缀和 + 哈兮

解题思路

• 考虑暴力解法，枚举以 \(i\) 结尾的长度为 \(firstLen\) 的子数组，求 \([i + 1, n - 1]\) 中长度为 \(secondLen\) 长度的子数组和的最大值，最后取两者和的最大值；
• 优化：前缀和 + 哈兮
  • 假设 \(firstLen\) 在 \(secondLen\) 的左边；
  • 可以初始化一个数组 \(left\) ，\(left[i]\) 表示 \([0, i]\) 中长度为 \(firstLen\) 的子数组的最大值，然后从右向左枚举长度为 \(secondLen\) 的子数组的左端点，计算当前长度为 \(secondLen\) 的子数组最大值 \(mx\)，\(res = max(res, mx + left[i])\)；
  • 然后在计算在右边的情况，两者取最大值。

代码

class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        int n = nums.size();
        vector<int> s(n + 1);
        for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1] + nums[i - 1];
        function<int(int, int)> getMax = [&](int L, int R) -> int {
            vector<int> left(n + 1);
            for (int i = L; i <= n; i ++ ) 
                left[i] = max(left[i - 1], s[i] - s[i - L]);
            int res = 0, mx = 0;
            for (int j = n - R; j >= 0; j -- ) {
                mx = max(mx, s[j + R] - s[j]);
                res = max(res, mx + left[j]);
            }
            return res;
        };
        return max(getMax(firstLen, secondLen), getMax(secondLen, firstLen));
    }
};

复杂度分析

时间复杂度：\(O(n)\)；
空间复杂度：\(O(n)\)。