Maximum subarray problem solved with divide and conquer also for the all negative element case

Question

Solving the maximum subarray problem with added cases of finding non maximum non contiguous subarray as well. I used divide and conquer approach and tackled the 'all negative' case by keeping a counter for that and branching it.

#include<stdio.h>
#include<limits.h>
#include<stdlib.h>

// finding maximum non contiguous  subarray by adding up all the non negative elements in array

int max_noncont_sub(int a[],int *lower, int *upper)
{
    int sum=0, i ;
for(i = *lower; i <= *upper; i++)
{
    if(a[i]>0)
        sum += a[i];    
}
return sum;
}

// finding max subarray which include the middle term, starting from mid and branching both sides till we encounter negative element

int max_cross_sub(int A[], int *lower, int mid, int *upper)
{
int left_sum = INT_MIN;
int sum = 0;
int i, max_left;

for(i = mid; i>=*lower; i--)
{
    sum = sum + A[i];
    if(sum>left_sum)
        left_sum = sum;
    max_left = i;
}

int right_sum = INT_MIN;
sum = 0;
int max_right;

for(i = mid+1; i<=*upper; i++)
{
    sum = sum + A[i];
    if(sum>right_sum)
        right_sum = sum;
    max_right = i;
}
*lower = max_left;
*upper = max_right;
return left_sum + right_sum;

}

//dividing the problem into 3 parts, left subarray and right have same substructure, 3rd one is solved by max_noncont_sub().

int max_sub(int A[], int *lower, int *upper)
{
    if(*lower == *upper)
    {
        return A[*lower];
    }   else
          {
               int mid = *lower + (*upper - *lower)/2;
               int left_low = *lower;
               int left_high = mid;
               int left_sum = max_sub(A, &left_low, &left_high);

               int right_low = mid+1;
               int right_high = *upper;
               int right_sum = max_sub(A, &right_low, &right_high);

               int cross_low = *lower;
               int cross_high = *upper;
               int cross_sum = max_cross_sub(A, &cross_low, mid, &cross_high);

               if(left_sum >=right_sum && left_sum>= cross_sum)
               {
                   *lower = left_low;
                    *upper = left_high;
                  return left_sum;
               } else if(right_sum >=left_sum && right_sum>= cross_sum)
                   {
                        *lower = right_low;
                        *upper = right_high;
                        return right_sum;
                   } else 
                       {
                            return cross_sum;
                        }


        }
 }

int main()
{
    int T, N, nc=0;
     scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&N);
        int *a = (int*)malloc(N*sizeof(int));
        int i;

        nc=0;
        for(i = 0; i<N; i++)
       {    
            scanf("%d",&a[i]);
            if(a[i]<0)
                nc++; // counting the negative numbers for later tackling with all negative special case
       }

    int lower = 0;
    int upper = N-1;

    if(nc == N)  // if all elements are negative, we just get the least negative and its the answer.
    {
        int max=INT_MIN;
        for(i =0;i<N;i++)
        {
            if(a[i]>max)
                max = a[i];
        }
        printf("%d %d\n",max, max);

    }
    else
    {
        printf("%d %d\n",max_sub(a, &lower, &upper), max_noncont_sub(a, &lower, &upper));
    }
 }
   return 0;
}

Any review and suggestions are welcome. Is there a better way to do it? I know there's kadane's algorithm with O(n) running time.

Answer 1

Bugs

1. Your sum in max_cross_sub() could overflow an int, causing a change in sign. Therefore, you could either miss the maximum subarray if your sum erroneously became negative, or get the wrong subarray if your sum erroneously became positive.

2. It seems that you want lower and upper to return the bounds of the maximum subarray. Otherwise you could just pass those arguments as regular integers instead of pointers. However, max_sub() doesn't set the correct bounds in the case of cross_sum being the max sum.

3. In addition to #2, max_cross_sub() doesn't set *lower and *upper to the correct bounds. The problem is that you don't set max_left and max_right correctly, so you end up leaving the bounds unchanged from whatever was passed in.

4. This line isn't right:

   printf("%d %d\n",max_sub(a, &lower, &upper), max_noncont_sub(a, &lower, &upper));
   

   The problem with it is that the call to max_sub() changes lower and upper, so that the call to max_noncont_sub() has the wrong bounds passed in. You should use two separate copies of the lower and upper bounds instead.

Better way

Clearly you already knew about Kadane's algorithm, because you mentioned it. The question is why you didn't use it? Not only is it faster, it's also only 6 lines of code compared to the roughly 60 lines you used to do it the divide and conquer way.