Hướng dẫn

Cố định i.
Gọi:

• pre[i] là tổng lớn nhất trong đoạn [1, i]
• suf[i] là tổng lớn nhất trong đoạn [i, n]

Đáp án bài toán là: max(pre[i-1] + suf[i], pre[i] + suf[i+1]), 2 ≤ i ≤ n - 1

Code: O(n)

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 1e5 + 5;
int n;
ll a[MAXN], pre[MAXN], suf[MAXN];
ll sum;

#define FOR(i,a,b)  for(int i=a; i<=b; ++i)
#define FORD(i,a,b) for(int i=a; i>=b; --i)

bool maximize(ll &a, const ll &b)
{
    return (a < b) ? a = b, 1 : 0;
}

signed main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    FOR(i,0,n+1) pre[i] = suf[i] = LLONG_MIN;

    sum = 0;
    FOR(i,1,n) 
    {
        cin >> a[i];
        sum += a[i];
        maximize(pre[i], pre[i-1]);
        maximize(pre[i], sum);
        maximize(sum, 0);
    }

    sum = 0;
    ll ans = LLONG_MIN;
    FORD(i,n,1)
    {
        sum += a[i];
        maximize(suf[i], suf[i+1]);
        maximize(suf[i], sum);
        maximize(sum, 0);

        if (i-1 >= 1) maximize(ans, pre[i-1] + suf[i]);
        if (i+1 <= n) maximize(ans, pre[i] + suf[i+1]);
    }

    cout << ans;
    return 0;
}