最大子数组题解

思路

先处理 $x<0$：把 $x$ 取反，同时把 $k$ 改为 $n-k$，就等价于交换“加”和“减”的位置，此后可设 $x\ge0$。

考虑最终选中的某个子数组，设长度为 $L$。为了使它的和最大，应尽量把加 $x$ 的位置放在子数组内，因此其中有 $\min(k,L)$ 个位置加 $x$。该子数组的最优贡献为原和加上

当 $L\le k$ 时，这等于在每个元素上加 $x$ 后求长度不超过 $k$ 的最大子数组；当 $L\ge k$ 时，这等于在每个元素上减 $x$ 后求长度不少于 $k$ 的最大子数组，再加 $2kx$。

做法

分别建立 $a_i+x$ 与 $a_i-x$ 的前缀和。

• 对长度不超过 $k$ 的部分，维护当前右端点前最近 $k$ 个前缀和的最小值，可用单调队列完成。
• 对长度不少于 $k$ 的部分，随右端点推进维护下标不超过 $r-k$ 的最小前缀和。

两部分与空子数组答案 $0$ 取最大值。

复杂度

每组测试的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。