Finding a maximum sum contiguous sub array

问题:

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

回答1:

There are a couple of problems with undefined behavior in your code:

The first is that you pass 9 as high which will be used to index the tenth element of an eight-element array. It will be the tenth because in cross_max you loop while i <= high, so you will index arr[9]. Remember that array indexes are from zero to the size minus one (so you can index from 0 to 7 for your array). The indexes out of bounds will contain undefined (i.e. random) values.

The second problem is that you are returning pointers to a local variable from cross_max. This will lead to undefined behavior when you use that returned pointer. Local variables are only valid inside the scope they were declared, and when the function returns the memory area used by the local variables will be reclaimed and used for the next function.

回答2:

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

回答3:

The algorithm is not very efficient. The time complexity is o(n^2). Here is a dynamic programming algorithm, which is o(n).

/*************************************************************************
    > File Name: subarray.cpp
    > Author: luliang
    > Mail: [e-mail] 
    > Created Time: 2013/09/10 Tuesday 15:49:23
 ************************************************************************/

#include <stdio.h>

typedef struct {
    int low;
    int high;
    int sum;
}DPInfoType;


int main()
{
    int arr[8] = {1,1,2,-2,3,3,4,-4};
    const int n = sizeof(arr) / sizeof(arr[0]);

    DPInfoType dp[n];
    dp[0].low = 0;
    dp[0].high = 0;
    dp[0].sum = arr[0];

    for(int i = 1; i < n; ++i) {
        if(dp[i - 1].sum > 0) {
            dp[i].low = dp[i - 1].low;
            dp[i].high = i;
            dp[i].sum = dp[i - 1].sum + arr[i];
        }
        else {
            dp[i].low = i;
            dp[i].high = i;
            dp[i].sum = arr[i];
        }
    }

    int max_index = 0;
    for(int i = 1; i < n; ++i) {
        if(dp[max_index].sum < dp[i].sum) max_index = i;
    }

    printf("\n Maximum sum = %d\n", dp[max_index].sum);
    printf("\n low = %d\n", dp[max_index].low);
    printf("\n high = %d\n", dp[max_index].high);

    return 0;
}

回答4:

As already mentioned use of pointers is inappropriate in your code. This code worked for me.

#include <stdio.h>
#define INF 1000000

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

int findMaxCrossingSubarray (int arr[], int low, int mid, int high, int *start, int *end)
{
    int i, left, right;
    int max_left, max_right;
    int left_sum = -INF;   
    int sum = 0;
    for (i = mid; i >= 0; i--) {
        sum += arr[i];
        if (sum > left_sum) {
            left_sum = sum;
            max_left = i;
        }
    }
    int right_sum = -INF;
    sum = 0;
    for (i = mid + 1; i <= high; i++) {
        sum += arr[i];
        if (sum > right_sum) {
           right_sum = sum;
           max_right = i;
        }
    }
    *start = max_left;
    *end = max_right;
    return left_sum + right_sum;
}

int findMaxSubarray (int arr[], int low, int high, int *start, int *end) 
{
    if (low == high) 
        return arr[low];

    int mid = (high - low)/2 + low;
    int start1, start2, start3;
    int end1, end2, end3;
    // initialization of start and end for terminal cases.
    start1 = start3 = low;
    start2 = mid + 1;
    end1 = mid;
    end2 = end3 = high;
    int sum1 = findMaxSubarray(arr, low, mid, &start1, &end1);
    int sum2 = findMaxSubarray(arr, mid + 1, high, &start2, &end2);
    int sum3 = findMaxCrossingSubarray(arr, low, mid, high, &start3, &end3);
    int res =  max(max(sum1, sum2), sum3);
    if (res == sum1) {
        *start = start1;
        *end = end1;
    }
    if (res == sum2) {
        *start = start2;
        *end = end2;
    }
    if (res == sum3) {
        *start = start3;
        *end = end3;
    }
    return res;
}

int main(int argc, char const *argv[])
{
    int size, i, item, result;
    printf("Enter the size of array: ");
    scanf("%d",&size);
    int arr[size];
    printf("Enter the array:\n");
    for (i = 0; i < size; ++i) {
        scanf("%d",&item);
        arr[i] = item;
    }
    int start = 0, end = size-1;
    result = findMaxSubarray(arr, 0, size-1, &start, &end);
    printf("Result: %d, start: %d and end: %d.\n", result, start, end);
    return 0;
}