最大子阵列的特例

Question

我使用分而治之来解决最大的子阵列问题。它在最常见的情况下工作正常但在特殊情况下失败。我认为问题可能发生在这里：

struct subarray maximum_crossing(int A[], int low, int mid ,int high){
    int left_sum = INT_MIN;
    int left_max = mid;
    int sum = 0;
    for (int i=mid; i >= low; i--){
        sum += A[i];
        if (sum > left_sum){
            left_sum = sum;
            left_max = i;
        };
    };
    ..........
    ..........

我测试它，它在常见情况下确实很好用。但是当数组看起来像这样：{-2147483648，-2147483648，-2147483648}时，它将返回最大子阵列从0开始并以1结束，并且最大值为0.我认为这是因为INT_MIN + INT_MIN将是C中0

或者在{-2147483648，-1,0}中，代码将发现最大子阵列从0开始，结束于1，最大值为2147483648.由于此问题，一旦数组具有-2147483648和其他负值，代码不起作用。

我尝试使用if语句首先检查A [i]的值，但我发现它不是最好的解决方案。因为其他负值仍然可以加在一起超过-2147483648。那么有没有更合适的方法来解决这种情况？

Answer 1

最大总和是2147483648

2147483648（十进制）是2 ^ 31，如果你的int是32位2147483648溢出为一个有符号的int，那么max_sum不能是2147483648

使用long（假设在64b上）为sum和left_sum