我使用分治法来解决最大子数组问题。 它在大多数常见情况下工作正常，但在特殊情况下失败。 我认为问题可能发生在这里:
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。那么对于这种情况有没有更合适的方法来解决呢？
最佳答案
max sum is 2147483648
2147483648(十进制)是 2^31，如果您的 int 是 32 位 2147483648 对于有符号 int 溢出，因此 max_sum 不能是2147483648
使用long(假设在64b上)作为sum和left_sum
关于c - 最大子数组的特殊情况，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54904737/