Tuesday, March 19, 2013

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();
}

Labels:

0 Comments:

Post a Comment

<< Home