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

这篇具有很好参考价值的文章主要介绍了【LeetCode】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。

提示:

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

这里简单介绍一下C++STL中的accumulate函数:

主要用来对指定范围内元素求和,但也自行指定一些其他操作,如范围内所有元素相乘、相除等。

  • 函数共有四个参数,其中前三个为必须,第四个为非必需。

  • 若不指定第四个参数,则默认对范围内的元素进行累加操作。

accumulate(起始迭代器, 结束迭代器, 初始值, 自定义操作函数)

如:计算数组中所有元素的和

#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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode力扣】189 53 轮转数组 | 最大子数组和

    目录 1、189. 轮转数组 1.1、题目介绍 1.2、解题思路 2、53. 最大子数组和 2.1、题目介绍 2.2、解题思路   原题链接: 189. 轮转数组 - 力扣(LeetCode) ​ 示例 1: 输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转

    2024年02月08日
    浏览(36)
  • leetcode 88 合并两个有序数组

    题目描述: 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应

    2024年02月03日
    浏览(46)
  • Leetcode. 88合并两个有序数组

    合并两个有序数组 核心思路: 依次比较,取较小值放入新数组中 i 遍历nums1 , j 遍历nums2 ,取较小值放入nums3中 那如果nums[i] 和nums[j]中相等,随便放一个到nums3 那如果nums[i] 和nums[j]中相等,随便放一个到nums3 此时 nums1 中的元素已经走完了,那么直接把 nums2 中剩下的元素拿到

    2023年04月08日
    浏览(99)
  • leetcode 152. 乘积最大子数组

    题目链接:leetcode 152 给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 子数组 是数组的连续子序列。 1)示例 1: 输入: nums = [2,3,-2,4] 输出: 6 解释: 子数

    2024年02月03日
    浏览(34)
  • LeetCode88——合并两个有序数组

    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。 为了应对这种情况

    2024年02月08日
    浏览(41)
  • 【Leetcode】88.合并两个有序数组

    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2 ,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意 :最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况

    2024年02月12日
    浏览(43)
  • LeetCode[53]最大子数组和

    Description: 给你一个整数数组  nums  ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组  是数组中的一个连续部分。 解法1:遍历--超时,内存超限,不通过,算法复杂度O(n^3)了吧 解法2:动态规划 这里有个关键状态转移方程的定义

    2024年01月25日
    浏览(62)
  • LeetCode刷题--- 最大子数组和

    个人主页: 元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏 力扣递归算法题   【C++】     ​​​​​​ 数据结构与算法  ​​​ 前言:这个专栏主要讲述动态规划算法,所以下面题目主要也是这些算法做的   我讲述题目会把讲解部分分为3个部分: 1、

    2024年01月23日
    浏览(67)
  • 两个数组的交集(LeetCode 349)

    题目 349. 两个数组的交集  思路         将较长的序列放入一个set后,再加入短序列的数字,判断当前数字是否添加成功,如果添加成功则表示set中没有该数字,则不属于两个数组之间的交集,将该数字从set中移除(移除是因为保证set的纯洁性 即只含有长序列中的数字);

    2024年02月11日
    浏览(57)
  • 【LeetCode】53. 最大子数组和

    这道题的状态设计和状态转移和 300. 最长递增子序列 类似。但是这里要求的是 连续子数组 ,和子序列不同。 状态定义 首先定义 dp[i] :以 nums[i] 结尾的具有最大和的连续子数组。 状态转移方程 根据状态的定义,dp[i] 一定包含 nums[i] 。 这里我们假设 nums[i] 0 ,则一定有 dp[

    2024年02月02日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包