题解

思路

先记原序列总和为 $S$。

做法

若选择区间 $[l,r]$，答案相对 $S$ 的增量为 $(C-1)\sum_{i=l}^r A_i$；不操作则对应增量 $0$。因此把每个 $A_i$ 乘上 $C-1$ 得到新序列，只需求这个新序列允许选择空段时的最大子段和。扫描时维护“以当前位置结尾的最大非负子段和”，并同步更新全局最大值即可。

所有计算使用 64 位整数。

复杂度

时间复杂度为 $O(N)$，额外空间复杂度为 $O(1)$。