又一个区间游戏 题解

思路

Bob 一定删除所选区间的最大元素，所以目标是最大化“区间和减区间最大值”。

做法

子任务 1

枚举左端点并扩展右端点，维护区间和与最大值，复杂度 $O(n^2)$。

子任务 2

全非负时扩大区间不会降低“区间和减最大值”，答案是全数组和减全数组最大值。

子任务 3

枚举区间最大值上界 $x\in[1,30]$。把大于 $x$ 的位置视为分隔点，在其余位置做最大子段和，候选为该子段和减 $x$。同时答案至少为 0。

正确性证明

引理 1 固定区间时 Bob 删除其最大元素最优。

证明 删除值越大，剩余和越小。∎

引理 2 枚举到某个最优区间最大值 $x$ 时，受限最大子段和至少取得该区间的和。

证明 最优区间所有元素不超过 $x$，不会被分隔，Kadane 枚举了它。∎

定理 算法输出最优得分。

证明 每个候选子段的最大值不超过枚举的 $x$，减去 $x$ 不会高估真实得分；由引理 2 又不会漏掉最优区间，故最大值准确。∎

复杂度

时间复杂度 $O(30n)$，空间复杂度 $O(1)$。