最大子段和

求数组中和最大的连续非空子段;前缀和最小值与 Kadane 扫描给出两种等价视角。

标签 算法 / 贪心 / 动态规划 / 前缀和 / 最大子段和

问题形式

给定长度为 𝑛 的整数序列 𝑎1,…,𝑎𝑛,求

max1≤𝑙≤𝑟≤𝑛∑𝑖=𝑙𝑟𝑎𝑖.

子段必须非空。若允许空子段,把答案与 0 取最大值即可。

前缀和视角

令

𝑃0=0,𝑃𝑖=∑𝑗=1𝑖𝑎𝑗.

区间 [𝑙,𝑟] 的和为 𝑃𝑟−𝑃𝑙−1。固定右端点 𝑟 时,需要让 𝑃𝑙−1 尽量小,其中 𝑙−1<𝑟。因此扫描时维护 𝑟 之前的最小前缀和即可:

𝐴=max𝑟(𝑃𝑟−min0≤𝑘<𝑟𝑃𝑘).

时间复杂度为 𝑂(𝑛)。

线性扫描

设 𝑒𝑖 为以 𝑖 结尾的最大子段和:

𝑒𝑖=max(𝑎𝑖,𝑒𝑖−1+𝑎𝑖).

答案为 max𝑖𝑒𝑖。若 𝑒𝑖−1<0,从 𝑖 重新开始不会更差。

判断 𝑒𝑖−1<0 的理由:以 𝑖−1 结尾的最优后缀已经是负数,把它接到 𝑎𝑖 前只会让和更小,不如直接从 𝑎𝑖 开始。

实现时维护当前和 𝐶 与答案 𝐴:把 𝑎𝑖 加入 𝐶;若 𝐶<0,令 𝐶=0,表示从下一个位置重新开始。注意 𝐴 要初始化为负无穷,以处理全负序列。

正确性

前缀和视角中,固定 𝑟 后,所有以 𝑟 结尾的子段对应 𝑃𝑙−1;取最小前缀和就得到以 𝑟 结尾的最大子段和。对所有 𝑟 取最大值,得到全局最大子段和。

线性扫描与它等价:𝑒𝑖 的递推覆盖了“从 𝑖 开始”和“接在某个以 𝑖−1 结尾的最优子段后”两种情况。

线段树维护区间最大子段和时,需要在每个结点保存区间和、最大前缀、最大后缀与最大子段和;具体应用见 最大 K 子段和。

源码位置