【算法题】53. 最大子数组和-力扣(LeetCode)
【算法题】53. 最大子数组和-力扣(LeetCode)
1.题目
下方是力扣官方题目的地址
53. 最大子数组和
给你一个整数数组 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
2.题解
思路
本题很显然可以用动态规划的思路
我们可以将该问题转换为子问题，找到这些子问题的状态转移方程
这个问题就可以轻松地解决了
我们用 dp[i] 代表以第 i个数结尾的连续子数组的最大和
dp[i]的得出有两种情况：
1.单独自成一个序列，从num[i]开始
2.加入dp[i-1]的那一段序列
由这两个情况可以很容易得出状态转移方程:
dp[i]=max(dp[i-1]+nums[i],nums[i])
得出了状态转移方程，这个问题也就迎刃而解了
Python代码
class Solution(object):def maxSubArray(self, nums):""":type nums: List[int]:rtype: int"""dp=[0]*len(nums) # 初始化dp数组dp[0]=nums[0]for i in range(1,len(nums)):dp[i]=max(dp[i-1]+nums[i],nums[i]) # 利用状态转移方程return max(dp)
3.结语
本人资历尚浅，发博客主要是记录与学习，欢迎大佬们批评指教！大家也可以在评论区多多交流，相互学习，共同成长。