分治法求解最大子数组的特殊溢出异常问题咨询

你的推测完全正确——问题根源就是带符号整数溢出的未定义行为。在C语言中，当两个int类型的负数相加超出int的最小值范围（比如INT_MIN + INT_MIN或INT_MIN + (-1)）时，会触发补码环绕，得到一个错误的正数，导致你的代码误判这个溢出值为更大的子数组和。

这里有两种可行的解决方案，其中第一种是最简洁可靠的：

方案一：使用更大范围的整数类型（推荐） #

直接用long long类型存储累加和与子数组和，从根本上避免溢出问题。因为long long的取值范围是-9223372036854775808到9223372036854775807，远大于int的范围，完全能容纳int数组元素累加的所有可能结果。

修改你的代码如下：

#include <limits.h>

// 先修改结构体，把sum字段改为long long类型
struct subarray {
    int start;
    int end;
    long long sum;
};

struct subarray maximum_crossing(int A[], int low, int mid, int high){
    long long left_sum = LLONG_MIN; // 使用long long的最小值
    int left_max = mid;
    long long sum = 0;
    for (int i=mid; i >= low; i--){
        sum += A[i];
        if (sum > left_sum){
            left_sum = sum;
            left_max = i;
        }
    }

    // 右侧部分同理修改
    long long right_sum = LLONG_MIN;
    int right_max = mid + 1;
    sum = 0;
    for (int j=mid+1; j <= high; j++){
        sum += A[j];
        if (sum > right_sum){
            right_sum = sum;
            right_max = j;
        }
    }

    struct subarray result;
    result.start = left_max;
    result.end = right_max;
    result.sum = left_sum + right_sum;
    return result;
}

这种方法不需要额外的溢出检查逻辑，代码简洁易维护，完全解决了溢出问题。

方案二：在相加前做溢出检查（不推荐，仅当必须使用int时） #

如果因为某些限制必须使用int类型，你需要在每次累加前判断是否会溢出。对于负溢出（我们场景中主要遇到的情况），判断逻辑是：当A[i]为负数时，如果当前sum小于INT_MIN - A[i]，说明sum + A[i]会超出int的最小值范围，触发溢出。

修改循环部分的代码示例：

for (int i=mid; i >= low; i--){
    int will_overflow = 0;
    if (A[i] < 0) {
        // 检查负溢出：sum + A[i] < INT_MIN
        if (sum < INT_MIN - A[i]) {
            will_overflow = 1;
        }
    } else if (A[i] > 0) {
        // 检查正溢出：sum + A[i] > INT_MAX
        if (sum > INT_MAX - A[i]) {
            will_overflow = 1;
        }
    }

    if (will_overflow) {
        // 溢出时，真实的和要么远小于INT_MIN，要么远大于INT_MAX
        // 对于负溢出，这个子数组的和不可能比当前left_sum大，直接跳过更新
        continue;
    } else {
        sum += A[i];
        if (sum > left_sum) {
            left_sum = sum;
            left_max = i;
        }
    }
}

这种方法需要额外的判断逻辑，容易遗漏边界情况，不如方案一可靠，仅作为特殊场景下的备选。

补充说明 #

你遇到的测试用例问题：

• 当数组全为INT_MIN时，两次INT_MIN相加溢出为0，代码误将这个0当成更大的和；
• 当数组为{-2147483648, -1, 0}时，INT_MIN + (-1)溢出为2147483647（补码环绕的结果），被误判为最大和。

使用方案一的long long类型后，这些溢出场景都会被正确处理，累加和会保持真实的负值，不会出现误判。

内容的提问来源于stack exchange，提问作者Kyle