不跨越和跨越里取最优解

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

const ll N = 2e5 + 5;
ll n;
ll a[N];

int main() {
    
    cin >> n;
    ll sum = 0;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    
    // 情况1：最大子段和（不跨边界）
    ll mx = -1e18;  // 全局最大
    ll cur = 0;     // 当前最大
    
    for (ll i = 1; i <= n; i++) {
        cur = max(cur + a[i], a[i]);
        mx = max(mx, cur);
    }
    
    // 情况2：跨边界 = 总和 - 最小子段和
    ll mn = 1e18;   // 全局最小
    ll cur2 = 0;    // 当前最小
    
    for (ll i = 1; i <= n; i++) {
        cur2 = min(cur2 + a[i], a[i]);
        mn = min(mn, cur2);
    }
    
    ll ans = max(mx, sum - mn);//max(不跨越时最大值，跨越时最大值)
    bool flag = true;//判断是否全为负数
    for (ll i = 1; i <= n; i++) {
        if (a[i] >= 0) {
            flag = false;
            break;
        }
    }
    
    if (flag) {
        ll maxv = -1e18;
        for (ll i = 1; i <= n; i++) {
            maxv = max(maxv, a[i]);
        }
        cout << maxv << endl;
    } else {
        cout << ans << endl;
    }
    
    return 0;
}