题解

题意
给定整数序列，求连续非空子数组的最大和。

---

思路
用贪心 Kadane 算法，维护当前段和、全局最大值。逐个遍历，每次选择另起一段或接上前段，不断更新最大值，一遍遍历即可求出答案，时间复杂度 O (n)。

---

完整代码

#include <bits/stdc++.h>
#define ll long long
#define qwq ios::sync_with_stdio(0), cin::tie(0), cout::tie(0)
using namespace std;

const int N = 1e5 + 5;
ll a[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    ll sum = a[1];
    ll maxn = a[1];
    for (int i = 2; i <= n; ++i) {
        sum = max(a[i], sum + a[i]);
        maxn = max(maxn, sum);
    }
    cout << maxn;
    return 0;
}