# DELISH.cpp

Dec 5th, 2021
825
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. using namespace std;
3.
4. typedef long long ll;
5.
6. ll cal(int n, vector<ll> &a) {
7.   vector<ll> l(n + 2), b(n + 2, LLONG_MIN);
8.   ll mi = 0;
9.   for (int i = 1; i <= n; i++) {
10.     l[i] = a[i] + l[i - 1];
11.     b[i] = max(l[i] - mi, b[i - 1]);
12.     mi = min(mi, l[i]);
13.   }
14.   vector<ll> r(n + 2), c(n + 2, LLONG_MAX);
15.   ll ma = 0;
16.   for (int i = n; i >= 1; i--) {
17.     r[i] = a[i] + r[i + 1];
18.     c[i] = min(r[i] - ma, c[i + 1]);
19.     ma = max(ma, r[i]);
20.   }
21.   ll res = 0;
22.   for (int i = 1; i <= n - 1; i++) {
23.     res = max(res, abs(b[i] - c[i + 1]));
24.   }
25.   return res;
26. }
27.
28. void solve() {
29.   int n; cin >> n;
30.   vector<ll> a(n + 2);
31.   for (int i = 1; i <= n; i++) {
32.     cin >> a[i];
33.   }
34.   ll ans = cal(n, a);
35.   reverse(a.begin() + 1, a.end() - 1);
36.   ans = max(ans, cal(n, a));
37.   cout << ans << '\n';
38. }
39.
40. signed main() {
41.   cin.tie(0)->sync_with_stdio(0);
42.   int T; cin >> T;
43.   while (T--) solve();
44. }
RAW Paste Data