0053. 最大子数组和 #

• 标签：数组、分治算法、动态规划
• 难度：简单

题目大意 #

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

解题思路 #

动态规划的方法，关键点是要找到状态转移方程。

假设 f(i) 表示第 i 个数结尾的「连续子数组的最大和」，那么 $max_{0 < i \le n-1} {f(i)} = max(f(i-1) + nums[i], nums[i])$

即将之前累加和加上当前值与当前值做比较， 如果将之前累加和加上当前值 > 当前值，那么加上当前值；如果将之前累加和加上当前值 < 当前值，那么 $f(i) = nums[i]$。

代码 #

1
2
3
4
5
6
7
8

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxAns = nums[0]
        ans = 0
        for num in nums:
            ans = max(ans + num, num)
            maxAns = max(maxAns, ans)
        return maxAns