文字教学

这道题是经典的最大子段和问题，使用Kadane算法在线性时间内解决。核心思路是：

1. 维护两个变量：cur 表示以当前位置结尾的最大子段和，ans 表示全局最大子段和。
2. 遍历数组时，对每个数决定是将其加入前一个子段，还是以它为起点开始新子段，取较大值更新 cur。
3. 每次更新 cur 后，用 cur 更新全局最大值 ans。

代码

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

const int N = 2e5 + 10;
int a[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    long long cur = a[0], ans = a[0];
    for (int i = 1; i < n; ++i) {
        cur = max((long long)a[i], cur + a[i]);
        ans = max(ans, cur);
    }
    cout << ans << endl;
    return 0;
}