求数组的最大连续子数组和。

核心回答

用 Kadane 动态规划一次扫描。令 end 表示“必须以当前位置结尾的非空连续子数组”的最大和；遇到 x 时，选择从 x 重新开始，或接到上一段后面，即 end=max(x,end+x)。再用 best 记录遍历过的最大 end，时间O(n)、额外空间O(1)。

初始化为第一个元素，才能正确处理全负数组；不能把答案初始为0，否则会错误地选择题目不允许的空子数组。

实现

下面按整数数组、至少取一个元素的条件实现；空输入显式抛出异常。

def max_subarray(nums):
    if not nums:
        raise ValueError("nums must be non-empty")
    end = best = nums[0]
    for i in range(1, len(nums)):
        x = nums[i]
        end = max(x, end + x)
        best = max(best, end)
    return best

没有用nums[1:]创建切片，因此额外空间保持O(1)。定长整数语言还要根据输入范围选择足够宽的累加类型。

为什么只保留这一段就够了

以i结尾的连续子数组，如果不只含nums[i]，就必须由一个以i-1结尾的子数组再加nums[i]构成。对所有候选都加同一个数时，之前较小的结尾和不会反超最大结尾和，因此一个end就能代表全部候选。

以[-2,1,-3,4,-1,2,1,-5,4]为例，end依次为-2、1、-2、4、3、5、6、1、5；best最终为6，对应[4,-1,2,1]。遇到-1时不必重开，因为前面4仍能贡献正收益。真正应丢弃的是负的累计前缀，而不是每个负元素。

对[-5,-2,-7]，end依次为-5、-2、-7，best为-2。单元素[3]直接返回3。

追问

如何返回区间？ 当x大于end+x时，记录新的候选起点；best变大时保存当前起点与i。若有并列最大值，需要先约定取最早、最短或任意一个。

还有别的推导吗？ 子数组和等于当前前缀和减去其左边的最小前缀和。扫描时先用已有最小前缀更新答案，再更新最小前缀，避免让左右端点相同而选到空段。

允许空子数组会怎样？ 此时全负数组可返回0，初始化和状态定义都应随之改变。它与本题的非空约束不同。

参考资料