【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 349)

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

    2024年02月11日
    浏览(48)
  • leetcode 349 两个数组的集合

    给定两个数组 nums1 和 nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 示例 1: 输入:nums1 = [1,2,2,1], nums2 = [2,2] 输出:[2] 示例 2: 输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出:[9,4] 解释:[4,9] 也是可通过的 这题比较简单,采

    2024年01月16日
    浏览(32)
  • LeetCode349. 两个数组的交集

    数组哈希.无序set都可以 给定两个数组 nums1 和 nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 示例 1: 输入:nums1 = [1,2,2,1], nums2 = [2,2] 输出:[2] 示例 2: 输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出:[9,4] 解释:[4,9] 也是可通

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

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

    2024年01月23日
    浏览(63)
  • LeetCode 0088. 合并两个有序数组

    力扣题目链接:https://leetcode.cn/problems/merge-sorted-array/ 给你两个按 非递减顺序 排列的整数数组  nums1 和 nums2 ,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意: 最终,合并后数组不应由

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

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

    2024年02月02日
    浏览(35)
  • leetcode 53. 最大子数组和

            要求找最大和的 连续子数组, 我的思路是 用一个temp记录局部最优值,用ans记录全局最优值。 然后在每次for循环进行一个判断:当前遍历元素+temp值 是否大于当前遍历元素的值,如果大于,说明temp值是帮了正忙的,所以让temp += 当前元素值;如果小于,说明temp是帮

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

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

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

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

    2024年02月12日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包