昨天微众T2和这个很像，浅浅回忆一下

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n;
int a[N], lmax[N], rmax[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int sum = a[1];
    lmax[1] = a[1];
    for (int i = 2; i <= n; i++) {
        sum = max(sum + a[i], a[i]);
        lmax[i] = max(lmax[i - 1], sum);
    }

    sum = a[n];
    rmax[n] = a[n];
    for (int i = n - 1; i; i--) {
        sum = max(sum + a[i], a[i]);
        rmax[i] = max(rmax[i + 1], sum);
    }

    for (int i = 1; i <= n; i++) cout << lmax[i] << ' ';
    puts("");
    for (int i = 1; i <= n; i++) cout << rmax[i] << ' ';
    puts("");
    int res = -1e9;
    for (int i = 1;i <= n; i++) 
        res = max(res, lmax[i] + rmax[i + 1]);
    cout << res <<  endl;

    return 0;
}