最大子段和
求数组中和最大的连续非空子段;前缀和最小值与 Kadane 扫描给出两种等价视角。标签 算法 / 贪心 / 动态规划 / 前缀和 / 最大子段和
问题形式
给定长度为 的整数序列 ,求
子段必须非空。若允许空子段,把答案与 取最大值即可。
前缀和视角
令
区间 的和为 。固定右端点 时,需要让 尽量小,其中 。因此扫描时维护 之前的最小前缀和即可:
时间复杂度为 。
线性扫描
设 为以 结尾的最大子段和:
答案为 。若 ,从 重新开始不会更差。
判断 的理由:以 结尾的最优后缀已经是负数,把它接到 前只会让和更小,不如直接从 开始。
实现时维护当前和 与答案 :把 加入 ;若 ,令 ,表示从下一个位置重新开始。注意 要初始化为负无穷,以处理全负序列。
正确性
前缀和视角中,固定 后,所有以 结尾的子段对应 ;取最小前缀和就得到以 结尾的最大子段和。对所有 取最大值,得到全局最大子段和。
线性扫描与它等价: 的递推覆盖了“从 开始”和“接在某个以 结尾的最优子段后”两种情况。
线段树维护区间最大子段和时,需要在每个结点保存区间和、最大前缀、最大后缀与最大子段和;具体应用见 最大 K 子段和。