2
\$\begingroup\$

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.

\$\endgroup\$
0

1 Answer 1

Reset to default
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ What is the good way to avoid and handle overflow like that as you mentioned in #1. Should I put checks on values attained by the variables so its sum doesn't overflow the sum? or some better way? thanks :) \$\endgroup\$ Commented Feb 2, 2016 at 10:38
  • \$\begingroup\$ @windlessStorm The easiest way is to use a larger type than int for your sum. For example, if your ints are 32-bit, use int64_t for your sum. If your ints are 64-bit, then you would need to do something more tricky (custom 128-bit math). For any size int, you can detect overflow from sign changes, but just detecting the overflow doesn't allow you to continue finding the max subarray (you need to actually hold the total sum) \$\endgroup\$ Commented Feb 2, 2016 at 19:14

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.