题解

思路

$N$ 为偶数时，无相邻限制的最优值是较大一半之和减较小一半之和；给较大一半标 +、较小一半标 -，任意同时含两种符号的串都有相邻异号对，反复删去即可达到该上界。

做法

$N$ 为奇数时，最终留下的只能是原序列奇数位置的元素；固定留下位置后，左右两段都是偶数长度，答案是两段上述最优值之和的最大值。

从左右分别扫描，用两个 multiset 维护当前段的较小一半、较大一半及其元素和，就能在 $O(\log N)$ 时间插入并在 $O(1)$ 时间取得“两半之差”。

复杂度

预处理偶数长度前缀与后缀的值，再枚举留下位置，时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。