【LeetCode53】最大子数组和(动态规划)

简介: (1)确定状态d p [ i ] dp[i]dp[i]表示nums中以nums[i]结尾子数组的最大子序和。

一、题目


image.png


二、思路

(1)确定状态

d p [ i ] dp[i]dp[i]表示nums中以nums[i]结尾子数组的最大子序和。


(2)状态转移方程(描述子问题之间的联系)

假设数组nums[i]值全部严格大于0,则一定有:

image.png

但是dp[i-1]可能是负数的,分类讨论:


如果dp[i-1]大于0,可以把nums[i]直接接在dp[i-1]表示的那个数组后面,构成当前最大连续子数组和dp[i],注意这里nums[i]可能大于0(加上去当然没问题),虽然也可能nums[i]小于0,也得加到dp[i-1]上,因为我们已经定义好了d p [ i ] dp[i]dp[i]表示nums中以nums[i]结尾子数组的最大子序和。;

如果dp[i-1]小于等于0,则nums[i]加在dp[i-1]上后并不会得到最大子序和,所以需要对当前的dp[i]另起炉灶,此时单独的nums[i]就是dp[i],但是注意这个dp[i]不一定是从开始到现在过程中的最大子序列和。

image.png

(3)边界条件 + 初始情况

只有第一个数字时:dp[0] = nums[0]

(4)计算顺序

从左往右,从下标0开始遍历。

三、 代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int>dp(n, 0);
        int ans = nums[0];
        dp[0] = nums[0];
        for(int i = 1; i < n; i++){
            dp[i] = max(dp[i-1] + nums[i], nums[i]);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};
相关文章
|
4月前
|
Go
【LeetCode 热题100】DP 实战进阶:最长递增子序列、乘积最大子数组、分割等和子集(力扣300 / 152/ 416 )(Go语言版)
本文深入解析三道经典的动态规划问题:**最长递增子序列(LIS)**、**乘积最大子数组** 和 **分割等和子集**。 - **300. LIS** 通过 `dp[i]` 表示以第 `i` 个元素结尾的最长递增子序列长度,支持 O(n²) 动态规划与 O(n log n) 的二分优化。 - **152. 乘积最大子数组** 利用正负数特性,同时维护最大值与最小值的状态转移方程。 - **416. 分割等和子集** 转化为 0-1 背包问题,通过布尔型 DP 实现子集和判断。 总结对比了三题的状态定义与解法技巧,并延伸至相关变种问题,助你掌握动态规划的核心思想与灵活应用!
146 1
|
6月前
|
机器学习/深度学习 算法 Go
【LeetCode 热题100】139:单词拆分(动态规划全解析+细节陷阱)(Go语言版)
本题是 LeetCode 热题 139:单词拆分(Word Break),需判断字符串 `s` 是否能由字典 `wordDict` 中的单词拼接而成。通过动态规划(DP)或记忆化搜索解决。DP 中定义布尔数组 `dp[i]` 表示前 `i` 个字符是否可拆分,状态转移方程为:若存在 `j` 使 `dp[j]=true` 且 `s[j:i]` 在字典中,则 `dp[i]=true`。初始条件 `dp[0]=true`。代码实现中用哈希集合优化查找效率。记忆化搜索则从起始位置递归尝试所有切割点。两种方法各有利弊,DP 更适合面试场景。思考扩展包括输出所有拆分方式及使用 Trie 优化大字典查找。
162 6
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
112 0
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
88 4
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
98 0
Leetcode第三十三题(搜索旋转排序数组)
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
187 0
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
80 0
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置

热门文章

最新文章