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