数据结构与算法 / 系统课时
推导连续子数组的最优值
推导连续子数组的最优值
最大子数组要求元素连续,真正关键的不是记录“前 i 个元素的最好答案”,而是记录“必须以当前位置结尾时的最好答案”。有了这个局部状态,是否延续上一段还是从当前位置重新开始,就能在一次扫描中决定。
学习目标
- 能解释为什么状态必须限定“以当前位置结尾”
- 能推导延续旧子数组与重新开始之间的转移条件
- 能正确处理全为负数的输入,并分析时间与空间复杂度
先固定结尾位置
设 end[i] 表示所有以 i 结尾的连续子数组中,元素和的最大值。因为子数组必须连续,到达 i 时只有两种选择:把 nums[i] 接在 end[i-1] 后面,或丢掉之前的部分,从 nums[i] 自己重新开始。
转移式因此是 end[i] = max(nums[i], end[i-1] + nums[i])。全局答案不是最后一个 end[i],而是扫描过程中所有 end[i] 的最大值。

如果 end[i-1] 是负数,把它带到当前位置只会让和变小,所以应重新开始;如果它是正数或 0,延续不会比单独取当前元素更差。这就是“负贡献时丢弃前缀”的严格依据。
跟踪一次状态变化
以 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 为例,end[i] 会依次得到 -2, 1, -2, 4, 3, 5, 6, 1, 5。其中最大值是 6,对应连续子数组 [4, -1, 2, 1]。
注意这里的局部状态可以下降。到 -5 时,end[i] 从 6 变成 1,但全局最优值仍然保留为 6。因此实现时通常需要两个变量:current 表示当前结尾状态,best 表示历史最大值。
用常数空间实现
下面是可直接运行的实现。初始化使用第一个元素,而不是 0,这样全为负数时仍会返回题目要求的非空子数组最大和。
def max_subarray_sum(nums):
if not nums:
raise ValueError("nums must not be empty")
current = nums[0]
best = nums[0]
for value in nums[1:]:
current = max(value, current + value)
best = max(best, current)
return best
if __name__ == "__main__":
values = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(values))预期输出:
6如果把 current 和 best 都初始化为 0,那么输入 [-5, -2, -8] 会错误返回 0,相当于偷偷允许了“空子数组”。当题目明确要求子数组非空时,状态初值必须来自真实元素。
为什么局部状态能支撑全局答案
“前 i 个元素的最大子数组和”本身不足以直接转移到 i+1,因为那个最优子数组可能早已在更左侧结束,无法保证与新元素连续。限定“必须以 i 结尾”后,状态才保留了下一步需要的结构信息。
这类设计体现了一个常见技巧:如果全局最优状态缺少可转移的信息,就给状态增加一个局部约束,使它能与下一阶段合法连接,再在所有局部状态上取全局最优。
复杂度与扩展
算法只扫描一次数组,时间复杂度为 O(n);current 和 best 两个变量足够,额外空间为 O(1)。若还要返回子数组的起止下标,可以在“重新开始”时记录候选起点,并在 best 更新时同步保存区间边界,核心转移不变。