题解 | 最大子段和

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 2e5 + 5;
using ll = long long;
ll a[N];
int main() {
    int n;
    cin >> n;
    a[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    ll ans = -1e11;
    ll now_min = 1e11;
    for (int i = 0; i <= n; i++) {
        ans = max(ans, a[i] - now_min);
        now_min = min(now_min, a[i]);
    }
    cout << ans << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

求子序列和，容易想到利用前缀和，a[i]-a[j](i>j)则得到区间[j-1,i]的区间和。

那么朴素想法就是两层循环，第一层循环i，第二层循环j，复杂度O(n*n)。

但实际第二层循环并不需要，我们要求最大值，只需记录当前最小值now_min即可，那么a[i]-now_min即为包含以a[i]为最后一个元素的最大区间和。