当前位置：首页 > article >正文

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

article 2024/11/19 22:40:37

题目：
给你一个整数数组 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题意：
给出一段数组，给出两个数字 l 和 r ，在数组中找到两端长度分别为 l 和 r 的不重叠的子数组，使得两段子数组的和加起来最大。

其实这道题的数据并不大，直接裸暴力就能过，就是固定一段长度为 l ，然后开始从头遍历所有长度为 r 的不重叠的子数组，不断更新res的最大值就好了。

那看了官方的题解，发现还可以用dp来做，所以发个题解来记录一下。

先讲一下dp的思路，再说dp和我们的暴力有什么不同之处。

因为是要得到 l 长度的和 r 长度的子数组的和最大，那就有两种情况，一种是 l 长度的数组在前，一种是 r 长度的数组在前。

我们以 l 长度的数组在前为例：

首先得到 0 ~ l-1 这段的和，作为suml，同时将maxsuml（l 长度的数组的最大的和）初始化为suml，也就是 l 长度的第一个数组和。

然后得到 l ~ l+r-1 这段的和，作为sumr，同时将res（答案）初始化为maxsuml+sumr。

然后开始移动。移动的策略就是，长度为 r 的数组每次向右移动一格，类似于滑动窗口，滑动的同时更新sumr。在移动的同时，将长度为 l 的数组也同时向右移动一格，也类似于滑动窗口，滑动的同时更新suml。与 r 不同之处在于， l 的数组在随着移动的时候，一直维持着maxsuml，也就是说，maxsuml一直是 r 左边的长度和最大的那个窗口的值，虽然 r 和 l 的窗口时不断向后移动的，但是maxsuml一直在维持，那移动到最终的数组末尾的时候，
res = max(res , maxsuml+sumr)

同理，在考虑一遍 r 在前 l 在后的情况，两者取最大值即是答案。

那我们的dp和暴力有什么不同之处呢？

显而易见，暴力是固定一个窗口大小，开始枚举另一个窗口的所有可能。而dp是两个窗口同时向后滑动，维持的是前面窗口的最大值。

代码：

class Solution {
public:
    int check(vector<int>nums , int l , int r){
        int suml = 0;    //前面l长度部分的和
        for(int i = 0 ; i < l ; i++)
            suml += nums[i];    //前面l长度部分的最大和
        int maxsuml = suml;        
        int sumr = 0;    //后面r长度部分的和
        for(int i = l ; i < l + r ; i++)
            sumr += nums[i];
        int res = maxsuml + sumr;
        for(int i = l+r , j = l ; i < nums.size() ; i++ , j++){
            suml += nums[j] - nums[j-l];
            maxsuml = max(maxsuml , suml);
            sumr += nums[i] - nums[i-r];
            res = max(res , maxsuml + sumr);
        }
        return res;
    }
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        return max(check(nums , firstLen , secondLen) , check(nums , secondLen , firstLen));
    }
};