tuki2501

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