LC53　最大子数组和¶

中等通过率 56.8%python3核心代码模式普通数组样例通过牛客 AC数组分治动态规划

讲解章节：线性 DP

一句话

Kadane 扫描：只维护「以当前位置结尾」的最大和，前缀为负就丢掉。

解题思路¶

这题考什么¶

枚举所有子数组是 O(n^2) 个区间，直接算和还要再乘一层。压下来的关键是换一个枚举方式：按右端点分类。记 f[i] 为「以下标 i 结尾的子数组里最大的和」，那么答案就是 max(f[0], f[1], …, f[n-1])——每个子数组都有唯一的右端点，这样分类不重不漏。

f[i] 只有两种可能：要么把 i 接到 f[i-1] 那个区间后面，要么从 i 自己重新起头。

f[i] = max(f[i - 1] + nums[i], nums[i])

等价的说法更好记：如果前面攒下的和已经小于等于 0，那它对后面只有拖累，直接扔掉从头再来。这就是 Kadane 算法（线性 DP 的最基础形态，见线性 DP）。

f 只用到前一项，不必开数组，一个变量滚动即可，空间降到 O(1)。

另一条路是前缀和（见前缀和与差分）：子数组和等于 pre[i + 1] - pre[j]，固定右端点求最大值就是让 pre[j] 最小，边扫边记录历史最小前缀和。这与 Kadane 是同一笔账的两种记法。题面进阶提到的分治做法（把区间劈两半，答案要么全在左、要么全在右、要么跨过中点，跨中点的那种从中点向两侧各扫一遍）是 O(n log n)，比 Kadane 慢，但它能扩展成线段树维护区间最大子段和，支持带修改的查询。

数据规模与复杂度¶

1 <= n <= 1e5，-1e4 <= nums[i] <= 1e4。时间 O(n)，空间 O(1)。和的绝对值上界 1e5 * 1e4 = 1e9，Python 整数不溢出（写 C++ 时要留意这已经逼近 int 的 2.1e9，改成 long long 更稳）。暴力枚举区间是 O(n^2) = 1e10 次运算，Python 下没有可能。

坑在哪¶

子数组至少含一个元素，不能返回空区间的 0。nums 全为负数时（如 [-3, -1, -2]）答案是其中最大的那个 -1，不是 0。把 best 初始化成 0 就会错答成 0；本题解把 best 与 cur 都初始化成 nums[0]，天然保证至少选了一个元素。
判断用 cur > 0 而不是 cur >= 0。cur 恰好为 0 时，接上去与重新起头算出的值相同，两种写法答案都对；但取 > 0 能让区间尽量短，语义更干净。
更新顺序必须是「先算完这一步的 cur，再拿它去更新 best」。反过来先更新 best 的话，最后一个元素带来的改进永远记不进去。
循环从下标 1 开始，因为下标 0 已经用来做初始化了。从 0 开始重复处理 nums[0]，会把它算进 cur 两次。
严格比对：答案是一个整数（最大和本身），不要求返回是哪个区间，没有多解。

样例复核¶

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]，期望 6。

i     0   1   2   3   4   5   6   7   8
nums -2   1  -3   4  -1   2   1  -5   4
cur  -2   1  -2   4   3   5   6   1   5
best -2   1   1   4   4   5   6   6   6

逐步看 cur：i=1 时前面的 cur = -2 不大于 0，丢掉，从 1 重开； i=2 接上得 1 + (-3) = -2；i=3 时 cur = -2 不大于 0，又丢掉，从 4 重开；此后一路累加到 i=6 的 6，正是区间 [4, -1, 2, 1]。最终 best = 6，与样例一致。

参考实现¶

solutions/leetcode/LC53/sol.py
from typing import List, Optional


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        # 两个变量都从 nums[0] 起步：子数组至少含一个元素，
        # 初始化成 0 会在全负数组（如 [-3, -1, -2]）上错答成 0
        best = nums[0]
        # cur 是循环不变量：处理完下标 i 之后，cur 恒等于「以 i 结尾的子数组的最大和」
        cur = nums[0]
        # 从下标 1 起，下标 0 已经在初始化里消化过了
        for i in range(1, n):
            if cur > 0:
                # 前面攒下的和是正的，接上去只会更大
                cur = cur + nums[i]
            else:
                # 前缀和非正，对后面只有拖累，整段丢掉，从 nums[i] 自己重新起头
                cur = nums[i]
            # 先算完 cur 再更新 best，顺序反了会漏掉最后一步带来的改进
            if cur > best:
                best = cur
        return best

LC53 最大子数组和¶