（13 分）设有 $n$ 个不全为负的整型元素存储在一维数组 A[p] 中，它包含很多连续的子数组，例如数组 A = {1, -2, 3, 10, -4, 7, 2, -5}，请设计一个时间上尽可能高效的算法，求出数组 A 的子数组之和的最大值（例如数组 A 的最大的子数组为 {3, 10, -4, 7, 2}，因此输出为该子数组的和 18）。要求：

(1) 给出算法的基本设计思想。 (2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。 (3) 说明你所设计算法的时间复杂度和空间复杂度。

信号量 复杂度分析

[tag_link]

**【答案】** (1) 基本设计思想：采用 Kadane 算法（动态规划思想）。遍历数组，维护两个变量：current_sum 记录以当前元素结尾的子数组的最大和，max_sum 记录全局最大子数组和。对于每个元素，若 current_sum 为负，则将其重置为当前元素值（因为负数会减小后续子数组的和），否则将当前元素加入 current_sum。然后更新 max_sum。遍历完成后，max_sum 即为所求。

(2) C 语言算法描述：

#include 
#include  // 使用 INT_MIN 初始化

int maxSubArray(int A[], int n) {
    int current_sum = 0;       // 当前子数组和
    int max_sum = INT_MIN;     // 最大子数组和，初始化为最小整数
    for (int i = 0; i < n; i++) {
        // 若当前子数组和为负，则从 A[i] 重新开始，否则累加
        if (current_sum < 0) {
            current_sum = A[i];
        } else {
            current_sum += A[i];
        }
        // 更新全局最大值
        if (current_sum > max_sum) {
            max_sum = current_sum;
        }
    }
    return max_sum;
}
`

(3) 时间复杂度：O(n)，其中 n 为数组长度，仅需一次遍历。空间复杂度：O(1)，仅使用常数个辅助变量。

**【解析】** 该算法基于动态规划，核心是确定以每个元素结尾的最大子数组和。设以元素 A[i] 结尾的最大子数组和为 f(i)，则状态转移方程为：f(i) = max(A[i], f(i-1) + A[i])。这是因为如果 f(i-1) 为负，其对 A[i] 无增益，故从 A[i] 重新开始；否则累加。算法中的 current_sum 即 f(i)，max_sum 记录所有 f(i) 的最大值。由于数组不全为负，max_sum 至少为非负，但算法也适用于全负情况。遍历一次即可求得结果，因此时间效率高，且仅需常数空间。