2025 年广州预赛

思路

离散分部求和又称 Abel 变换，是把 $\sum (x_{i+1}-x_i)M_i$ 重新分组为端点项减 $\sum x_i(M_i-M_{i-1})$。这是有限和的恒等变形，不需要单调假设；单调性用于后续解释最大值增量。

想法从哪来：差分可正可负，不能把前缀最大值简单替换成某个更大的数再逐项估计。应把整个和式做一次离散分部求和，让差分从原序列转移到前缀最大值序列。后者总是不减，更关键的是它只有在当前项创下新纪录时才会增长，因此增长那一步当前项就等于新的最大值。 这个事实把混合项变成“新最大值乘最大值增量”，可精确拆成相邻平方差与增量平方。平方差首尾相消，所有内部信息只留下非负平方和。最后还需区分末项是否创造新的最大值，因为目标中的总最大值可能来自末项，也可能停在前一步；两种情形分别配方，便不依赖原数列的正负。

逐项估计 $(x_{i+1}-x_i){\max }_{j\le i}{x}_j$ 会因差分可正可负而失效。改令 $M_i={\max }_{j\le i}{x}_j$，对差分和作离散分部求和；$M_i$ 只在 $x_i$ 创造新最大值时增加，这一结构会把所有内部项化成平方差。