BM72　连续子数组的最大和¶

简单通过率 39.48%python3核心代码模式样例通过牛客 AC贪心动态规划

牛客原题　源码

讲解章节：线性 DP

一句话

Kadane 算法：前面那段是负贡献就丢掉，从当前元素重新起头。

解题思路¶

这题考什么¶

最大子段和的经典状态设计，关键在于状态里必须钉住「以当前元素结尾」，见线性 DP。

状态定义：cur[i] = 以 a[i] 结尾的连续子数组的最大和。转移方程：

cur[i] = max(cur[i-1] + a[i], a[i])
ans    = max(cur[i])        对所有 i 取最大

两个候选分别是「把前面那段接上」与「从我这里另起一段」。等价的说法更好记：若 cur[i-1] <= 0，接上它只会拖后腿，直接扔掉重开。

为什么状态非要钉住结尾位置：只有钉住了，转移才只需要看前一格—— 「以 a[i] 结尾」的最优解必然由「以 a[i-1] 结尾」的最优解延伸或另起，无后效性成立。代价是最优子数组未必结尾在末位，所以答案必须每步取 max，而不是最后看 cur。

数据规模与复杂度¶

1 <= n <= 2e5，-100 <= a[i] <= 100，时限 2 秒（其他语言）。单趟扫描，时间 O(n)、空间 O(1)，达到题面进阶要求。和的绝对值上界 2e5 * 100 = 2e7，不涉及大整数。

坑在哪¶

数组可能全为负（a[i] 下界是 -100），而子数组长度至少为 1。 ans 必须用 array[0] 初始化，取 0 起手会让 [-10] 错答成 0。同理 cur 也从 array[0] 起手，然后从第二个元素开始扫。
答案要在每一步更新，不能循环结束后返回 cur——最优段大多不结尾在末位。
判据写 cur > 0 而不是 cur >= 0：cur == 0 时接不接都一样，两种写法结果相同，取严格大于少做一次无谓的延伸。
空数组返回 0 是防御性出口，题面保证 n >= 1。

样例复核¶

[1,-2,3,10,-4,7,2,-5]：cur 走过 1 -> -1 -> 3 -> 13 -> 9 -> 16 -> 18 -> 13，最大值 18，对应子数组 [3,10,-4,7,2]，与期望输出一致。

参考实现¶

solutions/nowcoder/BM72/sol.py
from typing import List, Optional


class Solution:
    def FindGreatestSumOfSubArray(self, array: List[int]) -> int:
        if not array:
            return 0
        # cur = 以当前元素结尾的最大和，ans = 全局最大。
        # 两者都从首元素起手：子数组长度至少为 1，取 0 会在全负数据上答错
        cur = ans = array[0]
        for x in array[1:]:
            # 前面那段是正贡献才接着用，否则从 x 重新起头（cur == 0 时两者等价）
            cur = cur + x if cur > 0 else x
            if cur > ans:
                ans = cur           # 每步都要更新：最优段未必结尾在末位
        return ans

BM72 连续子数组的最大和¶