分治法求最大子段和_c++分治法设计最大子段和

/*
1.分治算法
2.时间复杂度不超过O(nlogn) 
*/
#include<stdio.h>
#define N 50
int lefts,rights; 
int MAXSUM(int data[],int left,int right)
{
	int sum = 0;
	if(left == right)
	{
		sum = data[left]>0 ? data[left] : 0;
	}	
	else
	{
		int center = (left + right)/2;
		int leftsum = MAXSUM(data, left, center);
		int rightsum = MAXSUM(data, center+1, right);
		int S1 = 0,LEFT = 0;//LEFT从中间往两边走 
		for(int i = center; i >= left; i--)
		{
			LEFT += data[i];
			if(LEFT > S1)
			{
				S1 = LEFT;
				lefts = i;
			}
				
		}
		int S2 = 0,RIGHT = 0;
		for(int i = center+1; i <= right; i++)
		{
			RIGHT += data[i];
			if(RIGHT > S2)
			{
				S2 = RIGHT;
				rights = i;
			}
				
		}
		sum = S1 + S2;
		if(sum < leftsum)
		{
			sum = leftsum;
			lefts = left;
			rights = center;
		}
		if(sum < rightsum)
		{
			sum =rightsum;
			lefts = center+1;
			rights = right;
		}
			
	}
	return sum;	
}
int main()
{
	//输入数据 
	int n,data[N];
	printf("输入元素个数:\n"); 
	scanf("%d",&n);
	printf("输入数据:\n");
	for(int i = 0; i<n; i++)
	{
		scanf("%d",&data[i]);
	}
	int left=0,right=n-1; 
	//求最大字段和函数 
	int sum=MAXSUM(data,left,right);
	printf("最大子段和为：%d\n",sum);
	printf("开始下标为%d,结束下标为%d",lefts,rights);
 }
//-2 11 -4 13 -5 -2

主要算法：

        一分为二，先分别计算左边和右边的最大子段和，然后从中间往两边扩展计算最大字段和。左边、右边、从中间往两边取最大者为最大字段和！