OJ-leetcode-53. 最大子序和（简单动态规划）

亦凉 2022-10-23 08:20 20阅读 0赞

**目录**

题目

思路（错）

思路

代码

结果

--------------------

# 题目 #

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

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

示例 2：

输入：nums = \[1\]  
输出：1

**提示：**

*  `1 <= nums.length <= 3 * 104`
 *  `-105 <= nums[i] <= 105`

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/maximum-subarray

# 思路（错） #

dp\[i\]为只考虑前i个数时的连续子数组的最大和，最终结果为dp\[n-1\]

**状态之间无法转移**，即dp\[i\]不能由dp\[0\]...dp\[i-1\]表示

# 思路 #

dp\[i\]为**以nums\[i\]结尾**的连续数组的最大和，最终结果为max(dp\[i\]),0<=i<n。

加上“以nums\[i\]”结尾之后，就可以划分子问题了，划分为以nums\[i\]结尾，连接前面的以及不连接前面的仅nums\[i\]。如果dp\[i-1\]>0的话，连上前面的会更大，所以

dp\[i\] = dp\[i-1\]+nums\[i\], dp\[i-1\]>0

dp\[i\] = nums\[i\],dp\[i-1\]<=0

# 代码 #

class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            dp, res = nums[0], nums[0]
            if len(nums) == 1:
                return dp
            for num in nums[1:]:
                if dp > 0:
                    dp = dp + num
                else:
                    dp = num
                res = max(res, dp)
            return res

# 结果 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70][] 结果

更多内容：OJ网站题目分类，分难度整理笔记（leetcode、牛客网）

更多python相关内容：【python总结】python学习框架梳理

喜欢本文的请动动小手点个赞，收藏一下，有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70]: /images/20221023/4ad616b3398c4a88ad5fc0e603a38096.png