Maximum Subarray Problem - Recursive O(n log n) algorithm

I have implemented a recursive O(n log n) algorithm for solving the maximum sub-array problem. I would like a general review for it.

Here the max_subarray is the main function, and the static one is the auxillary function for it.

```
#include

int max_subarray(int array[], int low, int high);

static int max_crossing_subarray(int array[], int low, int mid, int high);

int main()
{
//The maximum subarray-sum is 43 for the following
int array[16] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
int low = 0;
int high = 15;

printf("%d", max_subarray(array, &low, &high));
printf("\n%d %d", low, high);

return 0;
}

int max_subarray(int array[], int low, int high)
{
if (low == high) {
return array[*low];
} else {
//Don't change avoids overflow
int mid = low + (high - *low)/2;

int left_low = *low;
int left_high = mid;
int left_sum = max_subarray(array, &left_low, &left_high);

int right_low = mid + 1;
int right_high = *high;
int right_sum = max_subarray(array, &right_low, &right_high);

int cross_low = *low;
int cross_high = *high;
int cross_sum = max_crossing_subarray(array, &cross_low, mid, &cross_high);

if (left_sum >= right_sum && left_sum >= cross_sum)
{
*low = left_low;
*high = left_high;
return left_sum;

} else if (right_sum >= left_sum && right_sum >= cross_sum) {
*low = right_low;
*high = right_high;
return right_sum;

} else {
*low = cross_low;
*high = cross_high;
return cross_sum;
}
}
}

static int max_crossing_subarray(int array[], int low, int mid, int high)
{
int left_sum = 0;
int max_left = mid;
for (int i = mid, sum = 0; i >= *low; i--) {
sum += array[i];
if (sum > left_sum) {
left_sum = sum;

Your program fails when all of the members of an array are negative, it simply returns 0 instead of the maximum negative number.

Recursion here is slowing you down. Using Kadane's algorithm, we can make the time complexity linear, or O(n) .

#include

#define max(a, b) (((a) > (b)) ? (a) : (b))

int maxSubArraySum(int array[], int size)
{
    int maxSoFar = array[0];
    int currentMax = array[0];

    for (int i = 1; i < size; i++)
    {
        currentMax = max(array[i], currentMax + array[i]);
        maxSoFar = max(maxSoFar, currentMax);
    }
    return maxSoFar;
}

int main()
{
    int array[] =  {-2, -3, 4, -1, -2, 1, 5, -3};
    int len = sizeof(array) / sizeof(array[0]);
    int maxSum = maxSubArraySum(array, len);
    printf("Maximum contiguous sum is %d\n", maxSum);
    return 0;
}

StackExchange Code Review Q#30489, answer score: 10