第13回 アルゴリズム実技検定 (PAST 013)

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];

    vll cumsum(N + 1), mi(N + 1);
    rep(i, N) {
        cumsum[i + 1] = cumsum[i] + A[i];
    }

    ll ans = -INF;
    rep2(i, 1, N + 1) {
        chmax(ans, cumsum[i] - mi[i - 1]);
        mi[i] = min(mi[i - 1], cumsum[i]);
    }
    cout << ans << endl;
}