#include <iostream>
#include <vector>
#include "../input.h"
using namespace std;

int recsum(int l, int r, vector<int>& A) {
    if (r - l == 0) {
        return 0;
    }
    if (r - l == 1) {
        return A.at(l);
    }

    int max;
    int max1 = recsum(l, (r+l)/2, A);
    int max2 = recsum((r+l)/2, r, A);
    int max3;

    int maxl = 0;
    int maxr = 0;

    int tmp = 0;
    for (int i = (r+l)/2; i < r; i++) {
        tmp += A.at(i);
        if (tmp > maxr) {
            maxr = tmp;
        }
    }

    tmp = 0;
    for (int i = (r+l)/2-1; i >= l; i--) {
        tmp += A.at(i);
        if (tmp >= maxl) {
            maxl = tmp;
        }
    }

    max3 = maxl + maxr;


    if (max3 >= max2) {
        max = max3;
    } else {
        max = max2;
    }
    if (max1 >= max) {
        max = max1;
    }

    return max;
}

int maxsum(vector<int>& A) {
    int max = recsum(0, A.size(), A);
    if (max <= 0) {
        max = 0;
    }
  return max;
}

int main() {
  Input();
  int size;
  while(cin >> size) {
    vector<int> v(size);
    for(int& x : v) cin >> x;
    cout << maxsum(v) << endl;
  }
  Diff();
}