给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。 输入格式 第一行是一个整数，表示序列的长度 n。 第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字 a_i 输出格式 输出一行一个整数表示答案。c++

这是一个常见的动态规划问题，可以使用 Kadane's Algorithm (卡尔曼算法) 来解决。Kadane's Algorithm 是用于寻找数组中局部最大和的有效方法，它遍历数组一次，维护两个变量：

1. `maxSoFar` 存储到目前为止遇到的最大连续子数组和。
2. `currentMax` 存储当前连续子数组的和。

当遍历数组时，对于每个元素，我们有两种选择：
- 如果当前元素加上 `currentMax` 大于0，说明开始一个新的子数组，这时更新 `currentMax` 为该元素的值。
- 否则，如果加上当前元素会使 `currentMax` 变成负数，那么从这个元素开始新的子数组更好，所以更新 `currentMax` 为该元素，`maxSoFar` 保持不变。

最后 `maxSoFar` 就是所求的最大子数组和。

以下是C++代码示例：

#include <iostream>
using namespace std;

int maxSubArray(int arr[], int n) {
    int maxSoFar = arr[0];
    int currentMax = arr[0];

    for (int i = 1; i < n; i++) {
        currentMax = max(arr[i], currentMax + arr[i]);
        maxSoFar = max(maxSoFar, currentMax);
    }

    return maxSoFar;
}

int main() {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "最大子数组和: " << maxSubArray(arr, n) << endl;
    return 0;
}