Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- ll cal(int n, vector<ll> &a) {
- vector<ll> l(n + 2), b(n + 2, LLONG_MIN);
- ll mi = 0;
- for (int i = 1; i <= n; i++) {
- l[i] = a[i] + l[i - 1];
- b[i] = max(l[i] - mi, b[i - 1]);
- mi = min(mi, l[i]);
- }
- vector<ll> r(n + 2), c(n + 2, LLONG_MAX);
- ll ma = 0;
- for (int i = n; i >= 1; i--) {
- r[i] = a[i] + r[i + 1];
- c[i] = min(r[i] - ma, c[i + 1]);
- ma = max(ma, r[i]);
- }
- ll res = 0;
- for (int i = 1; i <= n - 1; i++) {
- res = max(res, abs(b[i] - c[i + 1]));
- }
- return res;
- }
- void solve() {
- int n; cin >> n;
- vector<ll> a(n + 2);
- for (int i = 1; i <= n; i++) {
- cin >> a[i];
- }
- ll ans = cal(n, a);
- reverse(a.begin() + 1, a.end() - 1);
- ans = max(ans, cal(n, a));
- cout << ans << '\n';
- }
- signed main() {
- cin.tie(0)->sync_with_stdio(0);
- int T; cin >> T;
- while (T--) solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement