求最大子段和问题，分治递归法.txt

ACM资料大集合

#include <stdio.h>
#include <iostream.h>
#include <string.h>

//求最大子段和问题，分治递归法
/*
输入：
9
-20 11 3 -2 15 -30 12 1 5

输出：
27
*/
int maxsum(int s[],int left,int right)
{
	int center;
	int sumleft,sumright,sumcenter,s1,s2,i,temp;
	if(left==right) 
	{
		if(s[left]>0) sumcenter=s[left];
		else
			sumcenter=0;
	}
	else{
	center=(left+right)/2;
	sumleft=maxsum(s,left,center);
	sumright=maxsum(s,center+1,right);
	s1=temp=0;
	for(i=center;i>=left;i--)
	{
		temp+=s[i];
		if(s1<temp) s1=temp;
	}
	s2=temp=0;
	for(i=center+1;i<=right;i++)
	{
		temp+=s[i];
		if(s2<temp) s2=temp;
	}
	sumcenter=s1+s2;
	if(sumcenter<sumleft) sumcenter=sumleft;
	if(sumcenter<sumright) sumcenter=sumright;
	}
	return sumcenter;
}


int main()
{
	int s[10],num,i,answer;
	scanf("%d",&num);
	for(i=0;i<num;i++)
		scanf("%d",&s[i]);
	answer=maxsum(s,0,num-1);
	printf("answer=%d\n",answer);
	return 0;
}