题解

思路

先计算不翻转时的乘积和 $S$。固定翻转区间的中心后，区间每向两侧扩展一对位置，只会改变这两个 端点的配对关系。设端点为 $l,r$，扩展带来的变化为 $a_l b_r+a_r b_l-a_l b_l-a_r b_r$。

奇数长度区间与偶数长度区间的中心形式不同，分别枚举中心并向两侧扩展，即可覆盖所有连续区间。

做法

对每个位置枚举奇数长度翻转的中心，从相邻端点开始向外扩展；再对每对相邻位置枚举偶数长度中心。 维护当前区间翻转后的乘积和，并随时更新最大值。长度为一或不翻转都对应初始值 $S$。

正确性证明

任意连续区间都有唯一的中心：长度为奇数时中心是一个位置，长度为偶数时中心位于两个相邻位置之间。 算法分别枚举了两类所有中心，并对每个中心枚举所有可能半径，因此每个可翻转区间恰会被考察一次。

从较小半径扩展到端点 $l,r$ 时，内部元素的翻转配对保持不变，只有 $a_l,a_r$ 从原来的 $b_l,b_r$ 改为分别与 $b_r,b_l$ 配对。更新式准确给出乘积和变化。故算法计算了每个区间翻转后的 真实值，取最大值即为最优答案。

复杂度

所有中心总共扩展 $O(n^2)$ 对端点，时间复杂度为 $O(n^2)$，额外空间复杂度为 $O(n)$。