LeetCode刷题--- 最大子数组和-Toy模板网

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

状态显示
状态转移方程
初始化（防止填表时不越界）
填表顺序
返回值

状态显示

dp[i] 表示：以 i 位置元素为结尾的「所有子数组」中和的最大和。

状态转移方程

dp[i] 的所有可能可以分为以下两种：

子数组的长度为 1 ：此时 dp[i] = nums[i] ；
子数组的长度大于 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模板网！