最大子数组和

本文详细解析 LeetCode 53. 最大子数组和，提供前缀和与动态规划两种解法，包含思路说明和 Python 代码实现。

Leetcode Python 前缀和动态规划

题目

53. 最大子数组和 - 力扣（LeetCode）

解法一：前缀和

思路

前缀和数组 pre 存储从数组起始到每个位置的和。要计算子数组 [j, i] 的和，可以用 pre[i+1] - pre[j]。为了找到最大子数组和，我们需要在遍历过程中记录最小的前缀和 min_pre，这样当前前缀和减去最小前缀和就能得到以当前位置结尾的最大子数组和。

答案

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        pre = [0] * (len(nums) + 1)
        min_pre = 0
        res = nums[0]
        for i in range(1, len(nums) + 1):
            pre[i] = pre[i-1] + nums[i-1]
            res = max(res, pre[i] - min_pre)
            if pre[i] < min_pre:
                min_pre = pre[i]
        return res

解法二：动态规划（Kadane 算法）

思路

动态规划的核心是定义状态 max_sum 表示以当前元素结尾的最大子数组和。状态转移方程为：max_sum = max(nums[i], max_sum + nums[i])，即要么从当前元素重新开始，要么将当前元素加入之前的子数组。遍历过程中用 res 记录全局最大值。

答案

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = 0
        res = nums[0]
        for i in range(0, len(nums)):
            max_sum = max(nums[i], max_sum + nums[i])
            res = max(res, max_sum)
        return res