$O(N)$ 分治算法

#include <iostream> 
#include <algorithm>
#include <cstdio>
#include <cstring>
#define x first
#define y second
using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;
int n, a[N];
int sum[N], pred[N], succ[N];

PII work(int l, int r)
{
    if (l == r) {
        succ[l] = pred[l] = l;
        return PII(l, l);
    }

    int mid = (l + r) / 2;

    PII l_ans = work(l, mid);
    PII r_ans = work(mid + 1, r); 

    int ans_cross_mid = sum[pred[mid + 1]] - sum[succ[mid] - 1];
    int ans_left = sum[l_ans.y] - sum[l_ans.x - 1];
    int ans_right = sum[r_ans.y] - sum[r_ans.x - 1];

    int succ_update = sum[r] - sum[succ[mid] - 1];
    if (succ_update >= sum[r] - sum[succ[r] - 1]) {
        succ[r] = succ[mid];
    } 

    int pred_update = sum[pred[mid+1]] - sum[l-1];
    if (pred_update >= sum[pred[l]] - sum[l-1]) {
        pred[l] = pred[mid+1]; 
    }

    if (ans_left >= ans_right) {
        return (ans_left > ans_cross_mid) ? l_ans : PII (succ[mid], pred[mid + 1]);
    } else {
        return (ans_right > ans_cross_mid) ? r_ans : PII (succ[mid], pred[mid + 1]);
    }

}

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

    bool f = false;
    for (int i=1; i<=n; i++) 
        if (a[i] >= 0) {
            f = true;
            break;
        }
    if (!f) {
        cout << 0 << ' ' << a[1] << ' ' << a[n] << endl;
        return 0;
    }


    for (int i=1; i<=n; i++) sum[i] = sum[i-1] + a[i];
    PII ans = work(1, n); 

    //cout << ans.y << endl;
    int temp = 0, r_border = ans.y;
    for (int i=ans.y; i; i--) {
        temp += a[i];
        //cout << i << ' ' << temp << endl;
        if (temp == 0) r_border = i - 1; 
    }
    if (!r_border) r_border = ans.y;
    if (r_border < ans.x) r_border = ans.x;

    cout << sum[ans.y] - sum[ans.x - 1] << " " << a[ans.x] << " " << a[r_border] << endl;
    return 0;
}