Finding a maximum sum contiguous sub array

Question

I am writing a code to find the maximum sum contiguous sub array in C. The logic seems fine according to me, but still the output is not correct. Please look into the code. The algorithm divides a bigger array into 2 sub-arrays. It then checks for maximum sum sub-array by examining the left array , right array and also the array containing the midpoint (It will check right and left from the midpoint and then return the maximum sum sub-array containing the midpoint).

int* cross_max(int arr[], int low, int mid, int high)
{
    int left_max, left_sum = -2000;
    int sum = 0;
    int i;
    for(i=mid; i>=low;i--)
    {
        sum = sum + arr[i];
        if(sum > left_sum)
        {
            left_sum = sum;
            left_max = i;
        }
    }


    int right_max, right_sum = -2000;

    for(i=mid+1; i<=high;i++)
    {
        sum = sum + arr[i];
        if(sum > right_sum)
        {
            right_sum = sum;
            right_max = i;
        }
    }

    // 0 - sum
    // indices - 1,2

    int temp_arr[3] = {0,0,0};
    temp_arr[0] = left_sum + right_sum;
    temp_arr[1] = left_max;
    temp_arr[2] = right_max;

    int *p = temp_arr;

    printf("\n Maximum sum = %d\n",*p);
    printf("\n low = %d\n",*(p+1));
    printf("\n high = %d\n",*(p+2));    

    return p;

}


int* find_max(int arr[], int low, int high)
{
    int temp_arr[3] = {0,0,0};
    if(low == high)
    {
        temp_arr[0] = arr[low];
        temp_arr[1] = low;
        temp_arr[2] = low;

        int *q = temp_arr;
        return q;
    }

    int mid = (low + high)/2; 

    int* a1 =  find_max(arr,low,mid);
    int* a2 =  find_max(arr,mid+1,high);
    int* a3 =  cross_max(arr,low,mid,high);

    if (*a1 > *a2 && *a1 > *a3)
        return a1;

    else if (*a2 > *a1 && *a2 > *a3)
        return a2;

    else
        return a3;

}


int main()
{
    int arr[8] = {1,1,2,-2,3,3,4,-4};

    int *point = find_max(arr,0,7);

    printf("\n Maximum sum = %d\n",*point);
    printf("\n low = %d\n",*(point+1));
    printf("\n high = %d\n",*(point+2));    
    return 0;
}

Answer 1

Slightly off-topic, but this problem is well-known for the best way to solve it (in linear time). You can completely derive the code from the specification.

First, define the problem formally:

Given: integer array A[0, N)

Required:

max(0 <= p <= q <= N : sum(p, q)) 
    where sum(p, q) = sum(p <= i < q : A[i])

Approach:

Let X(n) = max(0 <= p <= q <= n : sum(p, q)), then we need to find X(N). We do this by induction:

X(0) = max(0 <= p <= q <= 0 : sum(p, q))
     = sum(0, 0)
     = sum(0 <= i < 0 : A[i])
     = 0

and

X(n+1) = max(0 <= p <= q <= n+1 : sum(p, q))
       = max(max(0 <= p <= q <= n : sum(p, q)), max(0 <= p <= n+1 : sum(p, n+1)))
       = max(X(n), Y(n+1))

where Y(n) = max(0 <= p <= n : sum(p, n)). We now also determine Y(n) by induction:

Y(0) = max(0 <= p <= 0 : sum(p, 0))
     = sum(0, 0)
     = 0

and

Y(n+1) = max(0 <= p <= n+1 : sum(p, n+1))
       = max(max(0 <= p <= n : sum(p, n+1)), sum(n+1, n+1)))
       = max(max(0 <= p <= n : sum(p, n)) + A[n], 0)
       = max(Y(n) + A[n], 0)

Code:

Using the analysis above, the code is trivial.

int arr[8] = {1,1,2,-2,3,3,4,-4};
int N = 8;

int x = 0;
int y = 0;

for (int n = 0; n < N; n++) {
    y = max(y + arr[n], 0);
    x = max(x, y);
}

printf("Maximum sum = %d\n", x);

with

int max(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}