最大子段和-分治法
/* 分治法思想:将一个n规模的问题分解成k个规模较小的子问题，并且这些子问题
之间都是相互独立的，通过递归求解这些子问题，然后将子问题的解合并，就可以
得到原问题的解。
用分治法求最大子段和首先将问题划分，即将一直序列划分成长度
相等的两个序列，这时会出现3种情况，即1:最大子段和在第一个序列，
2:最大子段和在第二个序列,3:最大子段和在第一个序列与第二个序列之间。
然后，将3种情况的最大子段和合并，取三者之中的最大值为问题的解。*/
#include
#include
int max_sum(int a[],int left,int right) ;
void main()
{
int i,n,a[100],t;
printf("请输入数列的个数(
scanf("%d",&n);
printf("请输入数列元素：\n");
for(i=1;i
scanf("%d",&a[i]);
t=max_sum(a,1,n);
printf("最大字段和是:%d\n",t);
}
//求序列a[left]~a[right]的最大子段和
int max_sum(int a[],int left,int right)
{
int i,j,sum=0;
int s1=0,s2=0,lefts=0,rights=0;
int center,leftsum,rightsum;
if(left==right)
{
if(a[left]>0)
sum=a[left];
else
sum=0;
}
else
{
center=(left+right)/2; //划分
leftsum=max_sum(a,left,center); //对应情况1，递归求解
rightsum=max_sum(a,center+1,right); //对应情况2，递归求解
//求解s1
for(i=center;i>=left;i--)
{
lefts=lefts+a[i];
if(lefts>s1)
s1=lefts;
}
//再求解s2
for(j=center+1;j
{
rights=rights+a[j];
if(rights>s2)
s2=rights;
}
sum=s1+s2; //计算情况3的最大子段和
if(sum
sum=leftsum;
if(sum
sum=rightsum;
}
return sum;
}