给你一个整数数组 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
这里简单介绍一下C++STL中的accumulate函数:
主要用来对指定范围内元素求和,但也自行指定一些其他操作,如范围内所有元素相乘、相除等。
-
函数共有四个参数,其中前三个为必须,第四个为非必需。
-
若不指定第四个参数,则默认对范围内的元素进行累加操作。
accumulate(起始迭代器, 结束迭代器, 初始值, 自定义操作函数)
如:计算数组中所有元素的和文章来源:https://www.toymoban.com/news/detail-430111.html
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
int main() {
vector<int> arr{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int sum = accumulate(arr.begin(), arr.end(), 0); // 初值0 + (1 + 2 + 3 + 4 +... + 10)
cout << sum << endl; // 输出55
return 0;
}
动态规划 + 滑动窗口:文章来源地址https://www.toymoban.com/news/detail-430111.html
class Solution {
public:
int help(vector<int>& nums,int firstLen,int secondLen){//滑动窗口
//初始化左窗口数值大小
int suml = accumulate(nums.begin(),nums.begin()+firstLen,0);
//滑动窗口,记录数据是否跟着滑动,记录最大数据
int max_suml = suml;
//初始化右窗口数值大小
int sumr = accumulate(nums.begin()+firstLen,nums.begin()+firstLen+secondLen,0);
//返回值
int res = sumr+max_suml;
//初始化窗口位置大小,开始滑动
for(int j = firstLen+secondLen,i=firstLen;j<nums.size();i++,j++){
//滑动之后左窗口的值
suml+=(nums[i]-nums[i-firstLen]);
//记录最大值,即值是否随着窗口滑动
max_suml=max(suml,max_suml);
//滑动之后右窗口的值
sumr+=(nums[j]-nums[j-secondLen]);
//获取窗口滑动前后俩子数组的最大值
res=max(res,max_suml+sumr);
}
return res;
}
int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {//first数组在second数组前或后,即左窗口或右窗口
return max(help(nums, firstLen, secondLen), help(nums, secondLen, firstLen));
}
};
到了这里,关于【LeetCode】1031. 两个非重叠子数组的最大和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!