LeetCode刷题--- 最大子数组和

这篇具有很好参考价值的文章主要介绍了LeetCode刷题--- 最大子数组和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏

力扣递归算法题

 

【C++】    

​​​​​​

数据结构与算法

 ​​​


前言:这个专栏主要讲述动态规划算法,所以下面题目主要也是这些算法做的  

我讲述题目会把讲解部分分为3个部分:
1、题目解析

2、算法原理思路讲解

3、代码实现


最大子数组和

题目链接:最大子数组和

题目

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

示例 1:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

示例 2:

输入:nums = [1]
输出:1

示例 3:

输入:nums = [5,4,-1,7,8]
输出:23

提示:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

解法

算法原理讲解

我们这题使用动态规划,我们做这类题目可以分为以下五个步骤文章来源地址https://www.toymoban.com/news/detail-818314.html

  1. 状态显示
  2. 状态转移方程
  3. 初始化(防止填表时不越界)
  4. 填表顺序
  5. 返回值

  • 状态显示
dp[i] 表示: 以 i  位置元素为结尾的「所有子数组」中和的最大和。
  • 状态转移方程
dp[i] 的所有可能可以分为以下两种:
  1. 子数组的长度为 1 :此时 dp[i] = nums[i]
  2. 子数组的长度大于 1 :此时 dp[i] 应该等于 以 i - 1 做结尾的「所有⼦数组」中和的最⼤值再加上 nums[i] ,也就是 dp[i - 1] + nums[i]
由于我们要的是「最⼤值」,因此应该是两种情况下的最⼤值,因此可得转移方程: dp[i] = max(nums[i], dp[i - 1] + nums[i]) 。
  • 初始化(防止填表时不越界)
在本题中,最前⾯加上⼀个格⼦,并且让 dp[0] = 0 即可。
  • 填表顺序
根据「状态转移⽅程」易得,填表顺序为「从左往右」。
  • 返回值
状态表示为「以 i 为结尾的所有⼦数组」的最⼤值,但是最大子数组和的结尾我们是不确定的。 因此我们需要返回整个 dp 表中的最⼤值。

代码实现

class Solution {
public:
    int maxSubArray(vector<int>& nums) 
    {
        int n = nums.size();

        int ret = INT_MIN;
        vector<int> dp(n+1);
        dp[0] = 0;

        for(int i = 1; i <= n; i++)
        {
            dp[i] = max(nums[i-1], dp[i-1] + nums[i-1]);
            ret = max(ret, dp[i]);
        }

        return ret;
    }
};

到了这里,关于LeetCode刷题--- 最大子数组和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 动态规划——最大子数组和(Leetcode 53)

    解题代码: ===== int maxSubArray(int* nums, int numsSize){ int pre = 0, maxAns = nums[0]; 自我介绍一下,小编13年上海交大毕业,曾经在小公司待过,也去过华为、OPPO等大厂,18年进入阿里一直到现在。 深知大多数Java工程师,想要提升技能,往往是自己摸索成长或者是报班学习,但对于培训

    2024年04月26日
    浏览(10)
  • leetcode410. 分割数组的最大值 动态规划

    hard:https://leetcode.cn/problems/split-array-largest-sum/ 给定一个非负整数数组 nums 和一个整数 m , 你需要将这个数组分成 m 个非空的连续子数组 。 设计一个算法使得这 m 个子数组各自和 的 最大值最小 。 令 dp[i][j]表示将数组的 前 i 个数分割为 j 组 所能得到的最大连续子数组和的最

    2024年02月13日
    浏览(12)
  • 老卫带你学---leetcode刷题(215. 数组中的第K个最大元素)

    给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 堆排序 对每个元素入堆,然后pop出来k-1个 这里需要注意,默认堆为最

    2024年02月07日
    浏览(17)
  • LeetCode刷题 | 1143. 最长公共子序列、1035. 不相交的线、53. 最大子数组和

    给定两个字符串  text1  和  text2 ,返回这两个字符串的最长  公共子序列  的长度。如果不存在  公共子序列  ,返回  0  。 一个字符串的  子序列   是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后

    2024年02月12日
    浏览(16)
  • LeetCode_动态规划_中等_918.环形子数组的最大和

    给定一个长度为 n 的环形整数数组 nums ,返回 nums 的非空子数组的最大可能和。 环形数组意味着数组的末端将会与开头相连呈环状。形式上, nums[i] 的下一个元素是 nums[(i + 1) % n] , nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。 子数组最多只能包含固定缓冲区 nums 中的每个元素

    2024年02月09日
    浏览(16)
  • 【LeetCode: 410. 分割数组的最大值 | 暴力递归=>记忆化搜索=>动态规划 】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2024年02月10日
    浏览(19)
  • 【LeetCode: 53. 最大子数组和 | 暴力递归=>记忆化搜索=>动态规划 | 分治法 】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2023年04月21日
    浏览(39)
  • (动态规划) 剑指 Offer 42. 连续子数组的最大和 ——【Leetcode每日一题】

    难度:简单 输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为 O(n) 。 示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 提示 : 1 = a r r . l e n g t h = 1 0 5 1 = arr.length = 10^

    2024年02月11日
    浏览(18)
  • LeetCode刷题笔记【23】:贪心算法专题-1(分发饼干、摆动序列、最大子序和)

    贪心的本质是选择每一阶段的局部最优,从而达到全局最优。 例如,有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿? 指定每次拿最大的,最终结果就是拿走最大数额的钱。 每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。 感觉像

    2024年02月09日
    浏览(19)
  • 算法leetcode|53. 最大子数组和(rust重拳出击)

    给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组 是数组中的一个连续部分。 1 = nums.length = 10 5 -10 4 = nums[i] = 10 4 面对这道算法题目,二当家的再次陷入了沉思。 刚开始以为要暴力破解,双循环什么的,但

    2024年02月08日
    浏览(18)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包