fork(1) download
copy 
  1. #include<iostream>
  2. #define ll long long
  3. using namespace std;
  4. const int nmax = 1e6;
  5. ll id[nmax + 5], lt[nmax + 5], rt[nmax + 5], s[nmax + 5], st[nmax + 5];
  6. int main(){
  7.     ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  8.     int n; cin >> n;
  9.     ll a[n + 1], s[n + 1]; s[0] = 0;
  10.     int tmp = 0;
  11.     for(int i = 1; i <= n; i++){
  12.         cin >> a[i];
  13.         s[i] = s[i - 1] + a[i];
  14.         if(s[i] >= s[tmp]) tmp = i;
  15.         id[i] = tmp;
  16.     }
  17.     ll res = s[n];
  18.     lt[0] = rt[n + 1] = 1e18;
  19.     for(int i = 1; i <= n; i++){
  20.         ll tt;
  21.         tt = s[i] - s[id[i]];
  22.         lt[i] = min(lt[i - 1], tt);
  23.     }
  24.     tmp = n + 1;
  25.     for(int i = n; i >= 1; i--){
  26.         st[i] = st[i + 1] + a[i];
  27.         if(st[i] >= st[tmp]) tmp = i;
  28.         id[i] = tmp;
  29.     }
  30.     for(int i = n; i >= 1; i--){
  31.         ll tt;
  32.         tt = st[i] - st[id[i]];
  33.         rt[i] = min(rt[i + 1], tt);
  34.     }
  35.     for(int i = 1; i < n; i++){
  36.         res = max(res, s[n] - 2 * (lt[i] + rt[i + 1]));
  37.     }
  38.     cout << res;
  39.  	return 0;
  40. }
  41.  
Success #stdin #stdout 0.01s 10248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
8623849455251196733
https://ideone.com/pFmJd2
language:
C++14 (gcc 8.3)
created:
15 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!