题解

思路推导

先计算不翻转时的偶数下标和 $base$。只有翻转长度为偶数的区间才会交换奇偶位置；奇数长度区间不会改变每个元素所在下标的奇偶性，因此没有收益。

若区间左端点为偶数、右端点为奇数，收益依次由 $a_1-a_0,a_3-a_2,\ldots$ 中的一段连续和组成。若左端点为奇数、右端点为偶数，收益依次由 $a_1-a_2,a_3-a_4,\ldots$ 中的一段连续和组成。

所以只需分别求这两个差分序列的最大非负子数组和，取较大者加到 $base$ 上。

做法

扫描原数组并构造两类相邻差分。对每一类用线性动态规划维护“以当前位置结尾的最大非负连续和”和全局最大值。最终输出基础和加两类最大收益中的较大者。

正确性证明

任意有效翻转若长度为奇数，所有元素的下标奇偶性不变，收益为零。若长度为偶数，其端点奇偶性不同；按左端点奇偶性分类，翻转造成的偶数位置变化恰好对应上述某个差分序列的一段连续和。

反过来，任一差分序列的连续段都对应一个端点奇偶性不同的原数组区间，翻转该区间即可取得这段差分和。因此所有可能的正收益与两个差分序列的连续段一一对应。

线性动态规划求得每个差分序列的最大非负连续段和，故取两者最大值后加上 $base$，得到所有合法操作中的最大答案。

复杂度分析

每组数据的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$；也可边扫描边计算到 $O(1)$ 额外空间。