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