# 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<stdio.h>

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;
max_left = i;
}
}

int right_sum = 0;
int max_right = mid;
for (int i = mid + 1, sum = 0; i <= *high; i++) {
sum += array[i];
if (sum > right_sum) {
right_sum = sum;
max_right = i;
}
}

*low = max_left;
*high = max_right;
return left_sum + right_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<stdio.h>

#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;
}

• Returning 0 is not unreasonable, if you consider an empty subarray to be a valid solution. Jan 5, 2014 at 9:38