fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  4. #define ll long long
  5. const int maxN = 1e5;
  6. int a[maxN];
  7.  
  8. ll recur(int l, int r){
  9.     if(l + 1 >= r) return a[l];
  10.  
  11.     int mid = (l + r) / 2;
  12.     ll ans = max(recur(l, mid), recur(mid, r));
  13.     ll ansL = LONG_LONG_MIN, ansR = LONG_LONG_MIN;
  14.     ll now = 0;
  15.     for(int i = l; i < mid; i++){
  16.         now += a[i];
  17.         ansL = max(ansL, now);
  18.     }
  19.     now = 0;
  20.     for(int i = mid; i < r; i++){
  21.         now += a[i];
  22.         ansR = max(ansR, now);
  23.     }   
  24.     ll sum = max(ansL, max(ansR, ansL + ansR));
  25.     ans = max(ans, sum);
  26.     cout << l << " " << r << " " << ansL << " " << ansR << endl;
  27.     return ans; 
  28.  
  29.  
  30.  
  31.  
  32.  
  33. }
  34. signed main(){
  35.     ios;
  36.     int n;
  37.     cin >> n;
  38.     for(int i = 0; i < n; i++){
  39.         cin >> a[i];
  40.     }
  41.     cout << recur(0, n) << endl;
  42. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5
3 -4 3 -1 2
stdout
copy 
3 5 -1 2
2 5 3 1
0 2 3 -4
0 5 3 4
7
https://ideone.com/jfPBbt
language:
C++14 (gcc 8.3)
created:
12 days 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!