给一个长为 \(n\) 的正整数数组，执行以下操作严格一次。
- 选择 \(l, r, (1 \leq l < r \leq n)\) ，任意一个正整数 \(k\) 。
- 重复 \(k\) 次：让 \([l, r]\) 的数组成环，按顺时针走一次。
希望 \(a_n - a_1\) 最大，找到这个数。
分类讨论题。
- 先判断 \(n\) 为 \(1\) 时 \(a_n - a_1\) 恒为 \(0\) ，因为以下操作至少需要两个数（迭代器可能越界）
- 选择的环不包括 \(a_1\) \(a_n\) ，则 \(a_n - a_1\) 恒不变
- 选择的环包括 \(a_1\) \(a_n\) ，则 \((a_n - a_1)_{max} = (a_{i + n - 1} - a_i)_{max}\) 。可以破环为链 \(O(n)\) 计算。
- 选择的环包括 \(a_1\) 不包括 \(a_n\) ，则 \((a_n - a_1)_{max} = max_{i=2}^{n} a_i - a_1\) 。
- 选择的环包括 \(a_n\) 不包括 \(a_1\) ，则 \((a_n - a_1)_{max} = a_n - min_{i=1}^{n-1} a_i\) 。
view
#include <bits/stdc++.h>
void solve() {
int n; std::cin >> n;
std::vector<int> a(n+1);
for (int i = 1; i <= n; i++) std::cin >> a[i];
int Max = a[n] - a[1];
if (n > 1) {
Max = std::max(Max, a[n] - *std::min_element(a.begin() + 1, a.begin() + n));
Max = std::max(Max, *std::max_element(a.begin() + 2, a.end()) - a[1]);
for (int i = 1; i <= n; i++) a.push_back(a[i]);
for (int i = 1; i <= n; i++) Max = std::max(Max, a[i + n - 1] - a[i]);
}
std::cout << Max << '\n';
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}