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;
}
There are a couple of problems with undefined behavior in your code:
The first is that you pass
9
ashigh
which will be used to index the tenth element of an eight-element array. It will be the tenth because incross_max
you loop whilei <= high
, so you will indexarr[9]
. Remember that array indexes are from zero to the size minus one (so you can index from0
to7
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.