以下题解来自

讲义第 72 页的减治策略

假设最大子序列和在子序列 $[a, b]$ 处取到，那么对于所有 $i \in [1, a - 1]$，必有 $\sum\limits_{j=i}^{a-1} S_j \le 0$，即以 $S_{a-1}$ 结尾的所有子序列之和均 $\lt 0$

有了这个性质，我们只需对每个元素 $S_i$，枚举以这个元素为结尾的子序列的最大和

一趟遍历，实时地维护一个子序列和 sum，每次令 sum += x（x 为当前元素），每当 $sum \lt 0$ 时将其置零（舍弃当前维护的子序列），那么 sum 即为以当前元素结尾的子序列的最大和

为什么呢？假设 sum 维护的子序列区间为 $[l, r]$，那么：

1. 对于所有 $i \in (l, r)$，都有 $\sum\limits_{j=l}^i S_j \ge 0$（否则被舍弃），则 $\sum\limits_{j=i}^r S_j \le \sum\limits_{j=l}^r S_j$；
2. 对于所有 $i \in [1, l)$，都有 $\sum\limits_{j=i}^{l - 1} S_j \lt 0$（否则不会被舍弃），则 $\sum\limits_{j=i}^r S_j \le \sum\limits_{j=l}^r S_j$。

此外需要注意全是负数的情况，此时答案应该是绝对值最小的那个负数。

#include <iostream>
using namespace std;
typedef long long ll;
const int inf = 1e9 + 5;
int main()
{
    int n;
    scanf("%d", &n);

    ll ans = -inf, sum = 0;
    for (int i = 1, x; i <= n; i++, sum = sum > 0 ? sum : 0)
        scanf("%d", &x), sum += x, ans = max(ans, sum);
    printf("%lld\n", ans);
}