题意概括

给定一个长度为 $N$ 的整数数组，要求找到其中一个和最大的连续子数组，并返回这个最大和。这个子数组必须至少包含一个元素。

数据范围:

• $1 \le N \le 10^5$
• 数组中的每个整数范围为 $[-10^4, 10^4]$

基础知识

本题是经典的 “最大子数组和” 问题，最著名的最优解法是 卡登算法 (Kadane's Algorithm)，这是一种动态规划思想的巧妙应用。

• 核心思想: 算法在一次遍历中完成求解。它主要维护两个核心变量：

  1. ans: 用来记录全局的最大子数组和，也就是我们最终的答案。
  2. cur: 用来记录以当前元素结尾的连续子数组的最大和。

• 状态转移: 当我们遍历到数组中的第 $i$ 个元素 a[i] 时，我们思考以 a[i] 结尾的子数组其最大和是多少。只有两种可能：

  1. 这个子数组就只包含 a[i] 这一个元素。
  2. 这个子数组是在以 a[i-1] 结尾的最大子数组的基础上，追加上 a[i]。

  所以，以 a[i] 结尾的最大和 cur 可以通过状态转移方程得出：

  $$cur_i = \max(a[i], cur_{i-1} + a[i])$$

  在遍历过程中，我们只需要一个变量 cur 来记录这个值。如果 cur 在加上当前元素后变为负数，那么它对后续的子数组和只会产生负贡献，因此我们不如从下一个元素重新开始计算，这等价于 cur = max(x, cur + x)。

• 更新全局最优解: 在每一步计算出新的 cur 后，我们都将它与全局最大和 ans 进行比较并更新 ans，即 ans = max(ans, cur)。

• 初始化: 由于数组元素可能全为负数，ans 必须被初始化为一个足够小的值（例如负无穷大），以保证能正确找到负数数组中的“最大”和（即最不负的那个值）。cur 可以初始化为0。

该算法的时间复杂度为 $O(N)$，空间复杂度为 $O(1)$，是解决此类问题的标准最优方案。

C++ 解决方案

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void slv() {
    int n;
    cin >> n;

    // ans 初始化为一个极小值，处理所有元素都是负数的情况
    ll ans = -1e18; 
    ll cur = 0;

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;

        // 决定是以当前元素x开始新的一段，还是将x加入上一段
        cur += x;
        if (cur < x) {
            cur = x;
        }
        
        // 更新全局最大和
        if (ans < cur) {
            ans = cur;
        }
    }

    cout << ans << endl;
}

int main() {
    // 关闭同步流，加速IO
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    slv();

    return 0;
}

/*
样例输入 1:
9
-2 1 -3 4 -1 2 1 -5 4

样例输出 1:
6

样例输入 2:
5
5 4 -1 7 8

样例输出 2:
23
*/