轮回只会影响两端时的 $A_1$ 或 $A_n$ ：
- 区间不含两端（ $1<l$ 且 $r<n$ ）： $A_1,A_n$ 不变， $S$ 不变，候选为 $A_1-A_n$ 。
- 前缀（ $l=1$ ）：可把任意 $A_k$ （ $1\le k\le r$ ）旋到首位，因此可达最大 $A_{\max}-A_n$ 。
- 后缀（ $r=n$ ）：可把任意 $A_k$ （ $l\le k\le n$ ）旋到末位，因此可达 $A_1-A_{\min}$ 。
- 整段（ $l=1,r=n$ ）：整体循环后 $S(A')=A_{i}-A_{i-1}$ （把相邻对视为环， $A_0=A_n$ ），因此可达 $\max_{2\le i\le n}(A_i-A_{i-1})$ 以及 $A_1-A_n$ （当环相邻对取 $(A\_1,A_n)$ ）。

P3408.第3题-符文轮回咒

1000ms

Difficulty: 4

所属公司 : 阿里

算法与标签>思维

题目内容

远古风语者在风之谷留下了一串符文，每个符文刻录着能量强度，记作 $A_1,A_2,...,A_n$ ;

他定义这串符文的 平滑度 为 $S(A)=\sum^{n-1}_{i=1}(A_i-A_{i+1})$

现风语者可对一段连续符文区间施展 轮回咒，即对区间 $[l,r]$ 进行一次或多次 循环右移：

恰好施展一次轮回咒后，得到新的符文序列 $A'$ 。请问能获得的最大平滑度 $max$ $S(A')$ 是多少?

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^4)$ ，表示测试组数；

除此之外，保证所有测试数据的 $n$ 之和不超过 $2×10^5$ 。

对于每组测试数据，新起一行输出一个整数，表示恰好执行一次轮回咒后能达到的最大平滑度。

输入

输出

1
3

说明

第一个样例中，将全段 $[1,3]$ 右移一步得到 { $3,1,2$ } ，平滑度 $(3-1)+(1-2)=1$ ；

第二个样例中，将区间 $[1,4]$ 右移三步得到 { $4,2,3,1$ } ，平滑度 $(4-2)+(2-3)+(3-1)= 3$ 。

输入

预期输出（选填）