18708 最大子段和

### 思路

为了找到一个整数序列中连续且非空的一段使得这段和最大，我们可以使用**Kadane's Algorithm**。该算法的时间复杂度为O(N)，适合处理大规模数据。

具体步骤如下：
1. 初始化两个变量：`max_current`和`max_global`，都设置为序列的第一个元素。
2. 从第二个元素开始遍历序列，对于每个元素`a[i]`：
   - 更新`max_current`为`max(a[i], max_current + a[i])`。
   - 更新`max_global`为`max(max_global, max_current)`。
3. 最终`max_global`即为所求的最大子段和。

### 伪代码

```
function find_max_subarray_sum(arr, n):
    max_current = arr[0]
    max_global = arr[0]

    for i from 1 to n-1:
        max_current = max(arr[i], max_current + arr[i])
        max_global = max(max_global, max_current)

    return max_global
```

### C++代码

#include <cstdio>
#include <algorithm>int find_max_subarray_sum(int arr[], int n) {int max_current = arr[0];int max_global = arr[0];for (int i = 1; i < n; ++i) {max_current = std::max(arr[i], max_current + arr[i]);max_global = std::max(max_global, max_current);}return max_global;
}int main() {int n;scanf("%d", &n);int arr[n];for (int i = 0; i < n; ++i) {scanf("%d", &arr[i]);}int result = find_max_subarray_sum(arr, n);printf("%d\n", result);return 0;
}

### 总结

通过使用Kadane's Algorithm，我们可以在O(N)的时间复杂度内找到最大子段和。该算法通过动态更新当前子段和和全局最大子段和，确保在遍历完数组后得到正确的结果。使用`scanf`和`printf`可以提高输入输出的效率，适合处理大规模数据。