结论题。
先给出结论，答案为 \(\max(\dfrac{1}{2}\sum\limits_{i=0}^{n-1}\left|a_i-a_{(i+1)\bmod n}\right|,\max\limits_{i=0}^{n-1}a_i)\)。
证明:记前者为 \(S\)，后者为 \(M\)。
- 当 \(S\lt M\)，发现不存在 \(a_i=0\)，那么将全体减 \(1\)，则 \(M\) 减 \(1\)。
- 当 \(S\gt M\)，选取全为 \(M\) 的连续区间减 \(1\)，则 \(S\) 减 \(1\)。
- 当 \(S=M\)，选取一段包含全部 \(M\) 的区间，但不能是整个环，减 \(1\)，则 \(S,M\) 均减 \(1\)。
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005;
int n;
ll a[N];
ll sum, mx;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]), mx = max(mx, a[i]);
for (int i = 1; i <= n; ++i) sum += abs(a[i] - a[(i - 1 > 0) ? i - 1 : n]);
sum /= 2;
printf("%lld", max(sum, mx));
return 0;
}