53. 最大子序和
来源: 53. 最大子序和
1. 题目描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
2. 解题思路
动态规划，每个位置为 max（前一个+这个位置，这个位置）
3. 代码
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
# 下面为nums长度至少为2的情况
res = nums[0] # 先设定一个初始值（假设第一个数是可获得的最小值）
for i in range(1, len(nums)):
nums[i] = max(nums[i], nums[i] + nums[i - 1]) # 更新后的nums[i]存储 以原始num[i]为结尾的子数组和的最大值
res = max(res, nums[i]) # 更新最大值
return res
