【学会动态规划】最大子数组和(19)

简介: 【学会动态规划】最大子数组和(19)

动态规划怎么学?

学习一个算法没有捷径,更何况是学习动态规划,

跟我一起刷动态规划算法题,一起学会动态规划!

1. 题目解析

题目链接:53. 最大子数组和 - 力扣(LeetCode)

题目很好理解,顾名思义,就是找最大的子数组和。

2. 算法原理

1. 状态表示

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

2. 状态转移方程

状态转移方程有两种情况,

1. 子数组长度为 1 时,最大和就是 i 位置的值

2. 子数组长度大于 1 是,最大和就是上一个位置的最大和 + 当前位置的值

所以我们就可以得出状态转移方程

dp [ i ] = max( nums[ i ],dp[ i ] + nums[ i ] )

3. 初始化

初始化就是防止越界,并且不影响后面的值,

初始化成 0 即可。

4. 填表顺序

从左往右即可。

5. 返回值

返回整个 dp 表里的最大值。

3. 代码编写

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n + 1);
        int ans = INT_MIN;
        for(int i = 1; i <= n ; i++) {
            dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果感到有所收获的话可以给博主点一个哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~

目录
打赏
0
0
0
0
339
分享
相关文章
【算法专题突破】双指针 - 三数之和(7)
【算法专题突破】双指针 - 三数之和(7)
68 0
【动态规划刷题 10】最大子数组和 III && 环形子数组的最大和
【动态规划刷题 10】最大子数组和 III && 环形子数组的最大和
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
4月前
|
【动态规划】子数组系列
本文介绍了多个动态规划问题及其解决方案,包括最大子数组和、环形子数组的最大和、乘积最大子数组、乘积为正数的最长子数组长度、等差数列划分、最长湍流子数组、单词拆分及环绕字符串中唯一的子字符串。通过详细的状态定义、转移方程和代码实现,帮助读者理解每类问题的核心思路与解题技巧。
67 2
|
4月前
|
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
91 0
【双指针问题】977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
60 0
Leetcode53/152—最大子数组和/最大子数组乘积(状态转移方程/不熟)
Leetcode53/152—最大子数组和/最大子数组乘积(状态转移方程/不熟)
120 0
leetcode 53 最大子数组和
leetcode 53 最大子数组和
67 0
leetcode 53 最大子数组和

热门文章

最新文章