力扣1031：两个非重叠子数组的最大和

给你一个整数数组 nums 和两个整数 firstLen 和 secondLen，请你找出并返回两个 非重叠 子数组 中元素的最大和，长度分别为 firstLen 和 secondLen 。
长度为 firstLen 的子数组可以出现在长为 secondLen 的子数组之前或之后，但二者必须是不重叠的。
子数组是数组的一个 连续 部分。

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

示例2：
输入：nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
输出：29
解释：子数组的一种选择中，[3,8,1] 长度为 3，[8,9] 长度为 2。

示例3：
输入：nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3
输出：31
解释：子数组的一种选择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。

思路：设长度为firstLen的子数组为a，长度为secondLen的子数组为b。两种情况：左a右b，左b右a。
先讨论左a右b，左b右a可同理。
从前往后枚举b的右端点（右端点从 firstLen+secondLen 开始，实际是b数组右端点的下一个，左闭右开区间方便利用前缀和计算子数组的和），过程中记录a的最大值，并每次更新 a+b 的最大值。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int n = nums.length;
        int[] s = new int[n + 1]; // 记录数组前缀和
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + nums[i];
        }
        return Math.max(f(s, firstLen, secondLen), f(s, secondLen, firstLen)); // 左a右b和左b右a取最大值
    }

    private int f(int[] s, int firstLen, int secondLen) {
        int maxSumA = 0; // 左边子数组的和,长度为secondLen,记下右移过程中的最大值
        int ans = 0; // 最大和
        for (int i = firstLen + secondLen; i < s.length; ++i) {
            int B = s[i] - s[i - secondLen]; // 右边子数组的和,长度为secondLen
            maxSumA = Math.max(maxSumA, s[i - secondLen] - s[i - secondLen - firstLen]);
            ans = Math.max(ans, maxSumA + B);
        }
        return ans;
    }
}

时间复杂度：O(n)