解题思路
暴力枚举
- 枚举所有断开位置 k=0…n−1（按0-based下标处理更方便）。
- 对于每个 k，线性扫描长度为 n 的序列，累加求出Sk。
- 取所有 Sk 的最大值即为答案。
由于 n≤2000，双重循环最多做 4×106 次乘加运算，完全可行。
P2944.第1题-小红的魔法环
题目内容
小红有一个长度为n的魔法环,环上依次有数字a1,a2,.,an。她希望通过切开魔法环并对线性序列应用加权
交替求和,得到最终魔法值。操作步骤如下:
1、选定一个断开位置k(1≦k≦n)，将环从此位置切开，得到线性序列
b1=ak,b2=ak+1,....bn−k+1=an,bn−k+2=a1,...,bn=ak−1.
2、对得到的线性序列{bj}计算加权交替求和:
S=1⋅b1−2⋅b2+3⋅b3−4⋅b4+...+(−1)n−1n⋅bn
小红希望在所有可能的断开位置中，S的值最大。请你计算并输出此最大值。
输入描述
第一行输入一个整数n(1≦n≦2000)，表示魔法环上的数字个数。
第二行输入n个整数a1,a2,...,an(0≦ai≦n),代表环上各位置的初始数字。
输出描述
输出一个整数，表示小红在所有断开位置的加权交替求和中能获得的最大魔法值。
样例1
输入
4
1 2 3 4
输出
4
说明
当断开位置k=2时,序列[2,3,4,1]的加权交替求和为
2−6+12−4=4,这是所有S中的最大值。
样例2
输入
5
1 4 2 3 5
输出
27
说明
当断开位置k=3时，序列[2,3,5,1,4]的加权交替求和为:
1×2−2×3+3×5−4×1+5×4=2−6+15−4+20=27为最大值
