力扣---1031. 两个非重叠子数组的最大和-JZTXT

给你一个整数数组 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。

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-sum-of-two-non-overlapping-subarrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一眼动规，虽然不知道到底该咋动规。。。

最近动规题挺多的，懵懵懂懂就写出来了，虽然还是没能弄清楚自己到底咋动规的。

可以发现，可以将当前数组分为左右两部分，分别存放 first 和 second 。

此时，可以想到利用辅助数组，分别存放当前位置前的最大值，以及后面的最大值。

又由于 first 和 second 的前后顺序不固定，所以还需要知道 second 在前，first 在后的情况。

代码如下：

class Solution {
    public int maxSumTwoNoOverlap (int[] nums, int firstLen, int secondLen) {
        int len = nums.length;
        int[][] dp1 = new int[len][2];
        int max1 = 0;
        int max2 = 0;
        int tem1 = 0;
        int tem2 = 0;
        for (int i = 0; i < len; i ++) {
            if (i >= firstLen) {
                tem1 += nums[i] - nums[i - firstLen];
                max1 = Math.max(max1, tem1);
            } else {
                tem1 += nums[i];
                max1 = tem1;
            }
            dp1[i][0] = max1;
            if (i >= secondLen) {
                tem2 += nums[i] - nums[i - secondLen];
                max2 = Math.max(max2, tem2);
            } else {
                tem2 += nums[i];
                max2 = tem2;
            }
            dp1[i][1] = max2;
        }
        // System.out.println(Arrays.deepToString(dp1));
        int[][] dp2 = new int[len][2];
        max1 = 0;
        tem1 = 0;
        max2 = 0;
        tem2 = 0;
        for (int i = len - 1; i >= 0; i --) {
            dp2[i][0] = max1;
            if (i + secondLen < len) {
                tem1 += nums[i] - nums[i + secondLen];
                max1 = Math.max(max1, tem1);
            } else {
                tem1 += nums[i];
                max1 = tem1;
            }
            dp2[i][1] = max2;
            if (i + firstLen < len) {
                tem2 += nums[i] - nums[i + firstLen];
                max2 = Math.max(max2, tem2);
            } else {
                tem2 += nums[i];
                max2 = tem2;
            }
        }
        // System.out.println(Arrays.deepToString(dp2));
        int res = 0;
        for (int i = 0; i < len; i ++) {
            res = Math.max(res, dp1[i][0] + dp2[i][0]);
            res = Math.max(res, dp1[i][1] + dp2[i][1]);
        }
        return res;
    }
}

由于两次的操作相同，只不过是改变了 firstLen 和 secondLen 的顺序。因此，可以用函数来简化代码。

而且也可以在从后往前给辅助数组添加数据时动态遍历。也可以直接节省掉第二个辅助数组的空间。

class Solution {
    public int maxSumTwoNoOverlap (int[] nums, int firstLen, int secondLen) {
        return Math.max(getRes(nums, firstLen, secondLen), getRes(nums, secondLen, firstLen));
    }

    private int getRes (int[] nums, int firstLen, int secondLen) {
        int len = nums.length;
        int[] dp = new int[len];
        int max = 0;
        int tem = 0;
        for (int i = 0; i < len; i++) {
            if (i >= firstLen) {
                tem += nums[i] - nums[i - firstLen];
                max = Math.max(max, tem);
            } else {
                tem += nums[i];
                max = tem;
            }
            dp[i] = max;
        }
        max = 0;
        tem = 0;
        int res = 0;
        for (int i = len - 1; i >= 0; i--) {
            res = Math.max(res, dp[i] + max);
            if (i + secondLen < len) {
                tem += nums[i] - nums[i + secondLen];
                max = Math.max(max, tem);
            } else {
                tem += nums[i];
                max = tem;
            }
        }
        return res;
    }
}