数据结构与算法 / 系统课时

推导连续子数组的最优值

推导连续子数组的最优值

最大子数组要求元素连续,真正关键的不是记录“前 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,这样全为负数时仍会返回题目要求的非空子数组最大和。

python
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))

预期输出:

text
6

如果把 current 和 best 都初始化为 0,那么输入 [-5, -2, -8] 会错误返回 0,相当于偷偷允许了“空子数组”。当题目明确要求子数组非空时,状态初值必须来自真实元素。

为什么局部状态能支撑全局答案

“前 i 个元素的最大子数组和”本身不足以直接转移到 i+1,因为那个最优子数组可能早已在更左侧结束,无法保证与新元素连续。限定“必须以 i 结尾”后,状态才保留了下一步需要的结构信息。

这类设计体现了一个常见技巧:如果全局最优状态缺少可转移的信息,就给状态增加一个局部约束,使它能与下一阶段合法连接,再在所有局部状态上取全局最优。

复杂度与扩展

算法只扫描一次数组,时间复杂度为 O(n);current 和 best 两个变量足够,额外空间为 O(1)。若还要返回子数组的起止下标,可以在“重新开始”时记录候选起点,并在 best 更新时同步保存区间边界,核心转移不变。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

推导连续子数组的最优值

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通