非重叠子数组的最大和 - MarsCode

官方题解

‬​​‬​​​​‬‌​​​​​‬‍‬​​‍​​​​​‍‍‬‬⁠​‬⁠​​​​‌​⁠​‌​​499. 非重叠子数组的最大和 - 飞书云文档

先说怎么求一个子数组的最大和。

用滑动窗口，这里用int subArrSum表示当前子数组和，int left表示左边界下标，int right表示右边界下标，这三个变量来维护滑动窗口。然后一次遍历，left从0遍历到n-subArrN，同时记录更新最大值。

然后这里求2个不重叠子数组的最大和，那就可以先固定一个子数组，剩下的数组元素中求另一个子数组最大和。然后动态迭代固定的第一个子数组。

具体实现上，可以先动态规划求出f1[i]表示左边界下标<= i 的n1长的子数组的最大和，以及f2[i + n1]求出左边界>= i + n1的n2长的子数组的最大和。

最大和的情况，可能是f1在前，f2在后，也可能是f2前f1后，所以要求这2种中更大的一个。

这样实现比先求出f2Left[i]表示i左边n2长子数组最大和，f2Right[i+n1]表示i+n1右边n2长最大子数组和，然后 滑动窗口迭代维护n1长的子数组的和，比较加上左边界f2Left或右边界f2Right谁更大的方法更优，因为边界情况能简化一些。

public class Main {
    public static int solution(int[] nums, int firstLen, int secondLen) {
        // PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE
        // write code here
        // 1.40
        return Math.max(subSolution(nums, firstLen, secondLen), 
                        subSolution(nums, secondLen, firstLen));
    }

    public static int subSolution(int[] nums, int firstLen, int secondLen) {
        // PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE
        // write code here
        // 1.40

        int n = nums.length;
        // 左边界<=i的子数组1最大和
        int[] subArr1MaxSum = new int[n - firstLen + 1];
        int l = 0;
        int r;
        int sum = 0;
        // 初始化
        for (r = 0; r < firstLen; r++) {
            sum += nums[r];
        }
        subArr1MaxSum[l] = sum;
        for (r = firstLen; r < n; r++) {
            sum += nums[r];
            sum -= nums[l];
            l++;
            subArr1MaxSum[l] = Math.max(subArr1MaxSum[l-1], sum);
        }

        // 左边界>=i的子数组2最大和
        int[] subArr2MaxSum = new int[n - secondLen + 1];
        r = n - 1;
        sum = 0;
        // 初始化
        for(l = n - 1; l >= n-secondLen; l--)
            sum += nums[l];
        subArr2MaxSum[l+1] = sum;
        for(l = n - secondLen - 1; l >= firstLen; l--) {
            sum += nums[l];
            sum -= nums[r];
            r--;
            subArr2MaxSum[l] = Math.max(subArr2MaxSum[l+1], sum);
        }

        //求最大和
        int ans = 0;
        for (int index = 0; index <= n - firstLen - secondLen; index++) {
            ans = Math.max(ans, subArr1MaxSum[index] + subArr2MaxSum[index+firstLen]);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(solution(new int[]{0, 6, 5, 2, 2, 5, 1, 9, 4}, 1, 2) == 20);
        System.out.println(solution(new int[]{3, 8, 1, 3, 5, 2, 1, 0}, 3, 2) == 21);
        System.out.println(solution(new int[]{2, 1, 4, 3, 5, 9, 5, 0, 3, 8}, 4, 3) == 33);
    }
}