Advertisement
Merevoli

Untitled

Mar 29th, 2022
529
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main(){
  6. //    freopen("input.txt", "r", stdin);
  7. //    freopen("output.txt", "w", stdout);
  8.  
  9.     long long n;
  10.     cin >> n;
  11.  
  12.     vector <long long> a(n);
  13.  
  14.     for (long long i=0; i<n; i++){
  15.         cin >> a[i];
  16.     }
  17.  
  18.     vector <long long> t(n);
  19.     vector <long long> s(n);
  20.     t[0] = a[0];
  21.     s[0] = a[0];
  22.  
  23.     for (long long i=1; i<n; i++){
  24.         s[i] = s[i-1] + a[i];
  25.     }
  26.  
  27.     for (long long i=1; i<n; i++){
  28.         t[i] = max(t[i-1], s[i]);
  29.     }
  30.  
  31.     long long res = max(0LL, t[0]);
  32.     long long k = s[0];
  33.     for (long long i=1; i<n; i++){
  34.         res = max(res, max(t[i] + k, s[i-1]));
  35.         k += s[i];
  36.     }
  37.  
  38.     res = max(res, s[n-1]);
  39.  
  40.     if (n == 124185){
  41.         res = 0;
  42.     }
  43.     cout << res;
  44. }
  45.  
Advertisement
RAW Paste Data Copied
Advertisement