TikTok 最大子数组和：以当前位置结尾的状态

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练求非空连续子数组最大和，输入非空；返回数值，空输入拒绝。

解题路线

1. ending 表示以当前项结束的最优非空子数组。它只能从当前值重新开始或接在上一 ending 后，故 max(x,ending+x)。
2. best 汇总每个结束位置的最优值，所有非空子数组都有一个结束位置，因此不会漏解。
3. 初始值用首项而非0，才能让全负输入选最大单项。只保存两个标量即可，避免不必要数组切片。
4. 若输出左右端点，重新起点时记录 start，best 改善时保存区间；平局要约定最短、最早或任意。

手动走一遍

[-4,-2,-8] 得-2；[-2,1,-3,4,-1,2,1,-5,4] 得6，对应4,-1,2,1。不是最大子序列和，不能跳过中间负项后继续按连续数组计。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def maximum_subarray(values):
    """Maximum sum of a nonempty contiguous subarray."""
    if not values:
        raise ValueError('nonempty input required')
    items = iter(values)
    ending = best = next(items)
    for value in items:
        ending = max(value, ending + value)
        best = max(best, ending)
    return best

复杂度

O(n) 时间、O(1) 工作空间，不计算输入存储。返回路径另加端点常数状态。

易错点与追问

容易失分的边界

• 初始化0错误允许空数组。
• 混同不连续子序列。
• 只在正数时更新最优。

继续深挖

• 如何返回索引并定义平局？
• 环形最大子数组如何额外处理？