1031. 两个无重叠子数组的最大和：前缀和数组 + 滑动窗口.md

题目简述：

给你一个整数数组 nums 和两个整数 firstLen 和 secondLen，请你找出并返回两个无重叠 子数组 中元素的最大和*，*长度分别为 firstLen 和 secondLen 。

长度为 firstLen 的子数组可以出现在长为 secondLen 的子数组之前或之后，但二者必须是无重叠。

子数组是数组的一个 连续 部分。

提示：

• 1 <= firstLen, secondLen <= 1000
• 2 <= firstLen + secondLen <= 1000
• firstLen + secondLen <= nums.length <= 1000
• 0 <= nums[i] <= 1000

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

思路

对于子数组和相关的问题，首先考虑前缀和数组 presum。

我们将长为 firstLen 的子数组记为 a、将长为 secondLen 的子数组记为 b。然后，不妨先假设 a 位于 b 的左侧，则当 b 是固定的时，最大和的 a 是能被确定的。这样，我们就将问题拆解为了若干个最大和子数组的子问题。

对于一个数组，要求解其和最大的定长子数组需要 $O(n)$ 的时间复杂度。现在，我们对数组中的所有可行点分别计算以该点作为起点所对应的子数组上的最大和定长子数组的和值，并计该和值序列为 fixedLenPresum。构建前缀和数组的时间复杂度为 $O(n)$，在拥有了前缀和数组后，假设已经计算了 $\forall i,\ i<j$ 的 fixedLenPresum[i] 的值，则计算 fixedLenPresum[j] 只需要付出 $O(1)$ 的时间复杂度开销，因为 $$ \text{fixedLenPresum}[j]=\max\big{\text{fixedLenPresum}[j-1],\ \text{presum}[j+1]-\text{presum}[j-\text{len}+1]\big} $$

这个式子可以视为一种很简单的 DP，这是为什么力扣上这道题有动态规划的标签。

于是，计算出 fixedLenPresum 序列只需要付出 $O(n)$ 的时间复杂度成本。

现在，我们再遍历索引，考虑每个点作为 b 终点的可能性，通过 fixedLenPresum，能够直接查表得到 b 起点左侧的长为 firstLen 的子数组的最大和。这样，经过一次完整的遍历，就能得到 a 位于 b 左侧的题设所要求的两个无重叠子数组的最大和。

若 b 位于 a 的左侧，同理，重复上述操作即可。

这样，我们就能在 $O(n)$ 的时间复杂度开销下，解决本问题。

但我不理解为什么力扣上本问题限定的数据范围是 firstLen + secondLen <= nums.length <= 1000，这差点引导我思考并设计 $O(n^2)$ 时间复杂度的算法。稍微一思考，发现完全可以实现线性时间复杂度的算法。

总的来看，我们的算法属于滑动窗口（存在定长窗口的双指针算法），结合了前缀和数组。

代码

算法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int n = nums.length;
        int[] presum = new int[n + 1];
        for (int i = 0; i < n; i++) presum[i + 1] = presum[i] + nums[i];

        int[] fixedFirstLenPresum = new int[n];
        int[] fixedSecondLenPresum = new int[n];
        int res = 0;
        // init
        fixedFirstLenPresum[firstLen] = presum[firstLen];
        fixedSecondLenPresum[secondLen] = presum[secondLen];

        for (int i = firstLen; i <= n - secondLen; i++) {
            fixedFirstLenPresum[i] = Math.max(fixedFirstLenPresum[i - 1], presum[i] - presum[i - firstLen]);
            res = Math.max(res, fixedFirstLenPresum[i] + presum[i + secondLen] - presum[i]);
        }
        for (int i = secondLen; i <= n - firstLen; i++) {
            fixedSecondLenPresum[i] = Math.max(fixedSecondLenPresum[i - 1], presum[i] - presum[i - secondLen]);
            res = Math.max(res, fixedSecondLenPresum[i] + presum[i + firstLen] - presum[i]);
        }

        return res;
    }
}