思路

• 轮回只会影响两端时的 $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)$）。

• 综上答案为下式四者最大：

  • $A_1-A_n$
  • $A_1-\min(A)$
  • $\max(A)-A_n$
  • $\max_{2\le i\le n}(A_i-A_{i-1})$

• 特判 $n=1$：答案为 $0$。

• 时间复杂度：$O(n)$（每组数据一次线性扫描）。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T;
	if (!(cin >> T)) return 0;
	while (T--) {
		int n;
		cin >> n;
		vector<long long> a(n);
		for (int i = 0; i < n; ++i) cin >> a[i];

		// 特判 n=1
		if (n == 1) {
			cout << 0 << "\n";
			continue;
		}

		long long mn = a[0], mx = a[0];
		for (int i = 1; i < n; ++i) {
			mn = min(mn, a[i]);
			mx = max(mx, a[i]);
		}

		// 候选1：原始 S(A) = A1 - An
		long long ans = a[0] - a[n-1];

		// 候选2：后缀旋转 -> A1 - min(A)
		ans = max(ans, a[0] - mn);

		// 候选3：前缀旋转 -> max(A) - An
		ans = max(ans, mx - a[n-1]);

		// 候选4：整段旋转 -> max(A_i - A_{i-1})，i=2..n
		for (int i = 1; i < n; ++i) {
			ans = max(ans, a[i] - a[i-1]);
		}

		cout << ans << "\n";
	}
	return 0;
}

Python

import sys

data = list(map(int, sys.stdin.read().strip().split()))
it = iter(data)
T = next(it, 0)

out_lines = []
for _ in range(T):
    n = next(it)
    a = [next(it) for _ in range(n)]

    # 特判 n=1
    if n == 1:
        out_lines.append("0")
        continue

    mn = min(a)
    mx = max(a)

    # 候选1：A1 - An
    ans = a[0] - a[-1]

    # 候选2：A1 - min(A)
    ans = max(ans, a[0] - mn)

    # 候选3：max(A) - An
    ans = max(ans, mx - a[-1])

    # 候选4：max(A_i - A_{i-1})
    for i in range(1, n):
        ans = max(ans, a[i] - a[i-1])

    out_lines.append(str(ans))

sys.stdout.write("\n".join(out_lines))

Java

import java.io.*;
import java.util.*;

public class Main {
	// 简单快读
	static class FastScanner {
		private final InputStream in;
		private final byte[] buffer = new byte[1 << 16];
		private int ptr = 0, len = 0;
		FastScanner(InputStream is) { in = is; }
		private int read() throws IOException {
			if (ptr >= len) {
				len = in.read(buffer);
				ptr = 0;
				if (len <= 0) return -1;
			}
			return buffer[ptr++];
		}
		long nextLong() throws IOException {
			int c; do { c = read(); } while (c <= ' ' && c != -1);
			long sgn = 1;
			if (c == '-') { sgn = -1; c = read(); }
			long x = 0;
			while (c > ' ') { x = x * 10 + (c - '0'); c = read(); }
			return x * sgn;
		}
		int nextInt() throws IOException { return (int) nextLong(); }
	}

	public static void main(String[] args) throws Exception {
		FastScanner fs = new FastScanner(System.in);
		StringBuilder sb = new StringBuilder();
		int T = fs.nextInt();
		while (T-- > 0) {
			int n = fs.nextInt();
			long[] a = new long[n];
			for (int i = 0; i < n; i++) a[i] = fs.nextLong();

			// 特判 n=1
			if (n == 1) {
				sb.append(0).append('\n');
				continue;
			}

			long mn = a[0], mx = a[0];
			for (int i = 1; i < n; i++) {
				if (a[i] < mn) mn = a[i];
				if (a[i] > mx) mx = a[i];
			}

			// 候选1：A1 - An
			long ans = a[0] - a[n - 1];

			// 候选2：A1 - min(A)
			ans = Math.max(ans, a[0] - mn);

			// 候选3：max(A) - An
			ans = Math.max(ans, mx - a[n - 1]);

			// 候选4：max(A_i - A_{i-1})
			for (int i = 1; i < n; i++) {
				ans = Math.max(ans, a[i] - a[i - 1]);
			}

			sb.append(ans).append('\n');
		}
		System.out.print(sb.toString());
	}
}

题目内容

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

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

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

• 每次循环右移一步将符文 $A_r$ ，移至位置 $l$ ，其余元素依次后移；

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

输入描述

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

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

输出描述

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

样例1

输入

2
3
1 2 3
4
1 4 2 3

输出

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$ 。