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.