题目内容

小红有一个长度为$n$的魔法环,环上依次有数字$a_1,a_2,.,a_n$。她希望通过切开魔法环并对线性序列应用加权

交替求和,得到最终魔法值。操作步骤如下:

1、选定一个断开位置$k(1≦k≦n)$，将环从此位置切开，得到线性序列

解题思路

暴力枚举

1. 枚举所有断开位置 $k=0\ldots n-1$（按0-based下标处理更方便）。
2. 对于每个 $k$，线性扫描长度为 $n$ 的序列，累加求出$S_k$。
3. 取所有 $S_k$ 的最大值即为答案。

由于 $n\le2000$，双重循环最多做 $4\times10^6$ 次乘加运算，完全可行。