力扣热门100题之最大子数组和【中等】【动态规划】

**力扣热门100题之最大子数组和**

**难度:** 中等**类型:** 动态规划**描述:**
给定一个整数数组 `nums`，返回其中 **最大连续子序列的总和**。

**示例1:**

输入:`nums = [-2,1,-3,4,-1,2,1,-5,4]`
输出:`6`

解释: 最大连续子序列为 `[4,-1,2,1]`，总和为 `6`.

**示例2:**

输入:`nums = [1]`
输出:`1`

**示例3:**

输入:`nums = [0]`
输出:`0`

**思路:**
最大子数组问题可以使用动态规划来解决。我们可以创建一个一维数组 `dp`，其中 `dp[i]` 表示以 `nums[i]` 为结尾的最大连续子序列的总和。

**代码实现:**

class Solution:
 def maxSubArray(self, nums):
 """
 :type nums: List[int]
 :rtype: int """
 # 初始化动态规划数组，dp[0] = nums[0]
 dp = [nums[0]]
 # 遍历数组，计算每个元素的最大连续子序列和 for i in range(1, len(nums)):
 # 如果当前元素大于前一个元素的最大连续子序列和，则更新dp[i]为当前元素本身 if nums[i] > dp[i-1]:
 dp.append(nums[i])
 # 否则，更新dp[i]为前一个元素的最大连续子序列和与当前元素的最大值之间的较大者 else:
 dp.append(max(dp[i-1], nums[i]))
 # 返回动态规划数组中的最大值，即最大子数组的总和 return max(dp)