题解，懒得写步骤

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
struct BIT {
    int size;
    vector<ll> tree;

    BIT(int n) : size(n), tree(n + 2, LLONG_MIN) {}
    void update(int idx, ll val) {
        while (idx <= size) {
            tree[idx] = max(tree[idx], val);
            idx += idx & -idx;
        }
    }
    ll query(int idx) const {
        ll res = LLONG_MIN;
        int current = idx;
        while (current > 0) {
            res = max(res, tree[current]);
            current -= current & -current;
        }
        return res;
    }
    ll query_range(int idx_start, int idx_end) const {
        return LLONG_MIN;
    }
};

int main(){
    int n;
    cin >> n;
    vector<ll> A(n);
    for(auto &x: A) cin >> x;
    vector<ll> S(n+1, 0);
    for(int i=1;i<=n;i++) S[i] = S[i-1] + A[i-1];
    vector<ll> sorted_S = S;
    sort(sorted_S.begin(), sorted_S.end());
    sorted_S.erase(unique(sorted_S.begin(), sorted_S.end()), sorted_S.end());
    auto get_idx = [&](ll x) -> int {
        return lower_bound(sorted_S.begin(), sorted_S.end(), x) - sorted_S.begin() +1;
    };
    int m = sorted_S.size();
    BIT bit1(m); 
    BIT bit2(m);
    vector<ll> Max3(m+1, LLONG_MIN);

    
    int idx0 = get_idx(S[0]);
    bit1.update(idx0, 0 - 0); 
    bit2.update(idx0, 0 + 0);
    Max3[idx0] = max(Max3[idx0], 0LL);
    ll dp_prev =0;
    vector<ll> dp(n+1, LLONG_MIN);
    dp[0] =0;

    for(int i=1;i<=n;i++){
        ll current_S = S[i];
        int idx = get_idx(current_S);
        ll Max1 = (idx >1) ? bit1.query(idx-1) : LLONG_MIN;

        struct SegTree {
            int n;
            vector<ll> tree;
            SegTree(int size){
                n =1;
                while(n < size) n <<=1;
                tree.assign(2*n, LLONG_MIN);
            }
            void update(int idx, ll val){
                idx +=n-1;
                tree[idx] = max(tree[idx], val);
                while(idx >1){
                    idx >>=1;
                    tree[idx] = max(tree[2*idx], tree[2*idx+1]);
                }
            }
            ll query(int l, int r){
                ll res = LLONG_MIN;
                l +=n-1;
                r +=n-1;
                while(l <= r){
                    if(l%2 ==1){
                        res = max(res, tree[l++]);
                    }
                    if(r%2 ==0){
                        res = max(res, tree[r--]);
                    }
                    l >>=1;
                    r >>=1;
                }
                return res;
            }
        };
        static SegTree* seg2 = nullptr;
        if(i ==1){
            seg2 = new SegTree(m);
            seg2->update(idx0, 0 +0);
        }
        ll max1 = (idx >1) ? bit1.query(idx-1) : LLONG_MIN;
        ll max2 = (idx <m) ? seg2->query(idx+1, m) : LLONG_MIN;
        ll max3 = Max3[idx];
        ll current_dp = LLONG_MIN;
        if(max1 != LLONG_MIN){
            current_dp = max(current_dp, max1 + (ll)i);
        }
        if(max2 != LLONG_MIN){
            current_dp = max(current_dp, max2 - (ll)i);
        }
        if(max3 != LLONG_MIN){
            current_dp = max(current_dp, max3);
        }

        dp[i] = current_dp;
        bit1.update(idx, dp[i] - (ll)i);
        seg2->update(idx, dp[i] + (ll)i);
        Max3[idx] = max(Max3[idx], dp[i]);

    }

    cout << dp[n] << "\n";
    return 0;
}