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

Question

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

Answer 1

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