思维题。
我们考虑每次 \(a\) 数组加一减一对于其前缀和 \(sum\) 的影响。
可以发现，假设相邻两次加一和减一的位置分别为 \(l\) 和 \(r\)，那么 \(sum\) 在 \([l,r)\) 内会加一。
先减后加也同理。
所以，一次加减操作相当于将 \(sum\) 若干段连续序列加一或减一。
而 \(sum\) 全部为 \(0\) 是 \(a\) 都变为 \(0\) 的充要条件。
因此我们只需要计算出 \(sum\) 归零的最小操作数，也就是 \(maxn-minn\)，其中 \(maxn\) 为最大正数，\(minn\) 为最小的负数。
复杂度 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T, n;
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> T;
while (T--) {
cin >> n;
ll sum = 0, minn = 0, maxn = 0;
for (int i = 1; i <= n; ++i) {
ll x; cin >> x; sum += x;
minn = min(minn, sum);
maxn = max(maxn, sum);
}
cout << maxn - minn << endl;
}
return 0;
}