Nhận xét: luôn tồn tại một cách chọn ~2~ đoạn ~l, r~ không giao nhau và vẫn đạt được kết quả tối ưu.

Như vậy, ta có thể xây dựng các mảng ~minLeft~ và ~minRight~ ý nghĩa:

• ~minLeft[i]~ là cách chọn ~1~ đoạn ~l, r~ sao cho ~r \leq i~ và tổng các phần tử thuộc đoạn ~l, r~ là nhỏ nhất có thể.

• ~minRight[i]~ là cách chọn ~1~ đoạn ~l, r~ sao cho ~i \leq l~ và tổng các phần tử thuộc đoạn ~l, r~ là nhỏ nhất có thể.

Đáp án của bài toán là giá trị ~Sum(a) - 2 \times (minLeft[i] + minRight[i + 1])~ lớn nhất với mọi giá trị ~i~ mà ~1 \leq i < n~. Trong đó, ~Sum(a)~ là tổng các phần tử dãy ~a~.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define For(i, a, b) for (int i=a;i<=b;++i)
#define Ford(i, a, b) for(int i=a;i>=b;--i)

#define cerr cout
#define deb(x) cerr << #x << ": " << x << endl
#define deba(a, x, y) cerr << #a << ": ", printA(a, x, y)
#define enter cerr << endl;
template<class A>
void printA(A a, int l, int r) {
    For(i, l, r) cerr << a[i] << " ";
    cerr << endl;
}

typedef long long ll;
typedef pair<int, int> ii;
typedef array<int, 3> arr;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

const int N = 2 * 1e5 + 5;



void solve()
{
    int n; cin >> n;
    vi a(n);
    for (int &x : a) cin >> x;
    if (n == 1) {
        cout << a[0];
        return;
    }
    vll minLeft(n), minRight(n);
    ll s = 0, ma = 0;
    for (int i = 0; i < n; ++i) {
        s += a[i];
        minLeft[i] = s - ma;
        if (i) minLeft[i] = min(minLeft[i], minLeft[i - 1]);
        ma = max(ma, s);
    }
    s = 0, ma = 0;
    for (int i = n - 1; i >= 0; --i) {
        s += a[i];
        minRight[i] = s - ma;
        if (i < n - 1) minRight[i] = min(minRight[i], minRight[i + 1]);
        ma = max(ma, s);
    }
    s = 0;
    for (int x : a) s += x;
    ll ans = max({s, s - 2 * minRight[1], s - 2 * minLeft[n - 2]});
    for (int i = 0; i < n - 1; ++i) {
        ans = max(ans, s - 2 * (minLeft[i] + minRight[i + 1]));
    }
    cout << ans;
}

int main()
{
//  freopen(".inp","r",stdin);
//  freopen(".out","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    solve();

    return 0;
}