用分治法求最大子段和.cpp

算法设计与分析的经典程序

#include <stdio.h>
#define M 1
int MSubSum(int *a,int left,int right)
{int ints,s1,s2,i,lefts,lefts2,center,rights,rights2;
 int sum = 0;
   if (left==right) sum = a[left]>0?a[left]:0;
   else{  center = (left+right)/2;
   lefts2 = MSubSum(a,left,center);
   rights2 = MSubSum(a,center+1,right);
  s1=0;
lefts=0;
for (i=center;i>=left;i--)
   {lefts+=a[i];
    if (lefts>s1) s1 = lefts;
        }
   s2=0;rights=0;
   for (i=center+1;i<=right;i++)
   {right+=a[i];
   if (rights>s2) s2 = rights;
   }
sum = s1+s2;
if(sum<lefts2) sum=lefts2;
	if( sum<right) sum=rights2;
	}
   return sum;
}
int MSum(int n,int *a)
{   
return MSubSum(a,1,n);
}
void main()
{int a[M]={-2,11,-4,13,-5,-2},n;n=6;
   printf("\n%10d\n",MSum( n,a));
}