题解 | 环形数组的连续子数组最大和

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

int main() {
    int n;
    cin >> n;
    long long total = 0;
    long long max_end = 0, min_end = 0;
    long long max_sum = LLONG_MIN, min_sum = LLONG_MAX;

    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        total += x;
        max_end = max(x, max_end + x);
        max_sum = max(max_sum, max_end);
        min_end = min(x, min_end + x);
        min_sum = min(min_sum, min_end);
    }

    if (max_sum < 0) {                 // 全为负数
        cout << max_sum << '\n';
    } else {
        cout << max(max_sum, total - min_sum) << '\n';
    }
    return 0;
}