Maximum Subarray Sum Source code:
//maximum crossing subarray
int mcs(int array[],int low, int mid,int high)
{
result res={0};
int i =0;
int left_sum = -100000;//INT_MIN;
int right_sum = -100000;//INT_MIN;
int sum = 0;
for(i=mid; i >= 0;i--)
{
sum += array[i] ;
if( sum > left_sum)
{
left_sum = sum;
}
}
sum = 0;
for(i=mid+1; i < high;i++)
{
sum += array[i] ;
if( sum > right_sum)
{
right_sum = sum;
}
}
return left_sum + right_sum;
}
int maximum(int a, int b, int c)
{
if( (a >= b) && (a >=c))
{
return a;
}
else if( (b >= a) && (b >=c))
{
return b;
}
return c;
}
int maxsum(int array[], int low,int high)
{
int max1,max2,max3;
if( low == high)
{
return array[low];
}
int mid = (low +high)/2;
max1= maxsum(array,low,mid);
max2= maxsum(array,mid+1, high);
max3= mcs(array,low,mid,high);
return maximum(max1,max2,max3);
}
void test()
{
int array[] = {31,-41,59,26,-53,58,97,-93,-23,84};
int arraySize = sizeof(array) / sizeof(array[0]) ;
printf("\n maximum subarray sum=%d",maxsum(array,0,arraySize-1));
}
void main()
{
test();
}
//maximum crossing subarray
int mcs(int array[],int low, int mid,int high)
{
result res={0};
int i =0;
int left_sum = -100000;//INT_MIN;
int right_sum = -100000;//INT_MIN;
int sum = 0;
for(i=mid; i >= 0;i--)
{
sum += array[i] ;
if( sum > left_sum)
{
left_sum = sum;
}
}
sum = 0;
for(i=mid+1; i < high;i++)
{
sum += array[i] ;
if( sum > right_sum)
{
right_sum = sum;
}
}
return left_sum + right_sum;
}
int maximum(int a, int b, int c)
{
if( (a >= b) && (a >=c))
{
return a;
}
else if( (b >= a) && (b >=c))
{
return b;
}
return c;
}
int maxsum(int array[], int low,int high)
{
int max1,max2,max3;
if( low == high)
{
return array[low];
}
int mid = (low +high)/2;
max1= maxsum(array,low,mid);
max2= maxsum(array,mid+1, high);
max3= mcs(array,low,mid,high);
return maximum(max1,max2,max3);
}
void test()
{
int array[] = {31,-41,59,26,-53,58,97,-93,-23,84};
int arraySize = sizeof(array) / sizeof(array[0]) ;
printf("\n maximum subarray sum=%d",maxsum(array,0,arraySize-1));
}
void main()
{
test();
}
Labels: max subarray sum
0 Comments:
Post a Comment
<< Home