学步园

问题描述：给定长度为n的整数序列，a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大.或者求出最大的这个和.例如(-2,11,-4,13,-5,2)的最大子段和为20,所求子区间为[2,4].

求子区间及其最大值，是非常适合采用分治法德算法设计思想来设计的，其分治的思想是把一个难以直接解决的大问题，分成一些规模较小的相同性质的问题，以便各个击破，分而治之。如果规模为N的问题可以分解成k个子问题（1<k<=N）,并且这些子问题之间相互独立，互不影响，递归地解决这些问题，然后合并这些子问题的解，得到最后问题的解。

分治法的代码实现过程如下：

int MaxSubSum(int a[],int left,int right)
{
	int sum = 0;		//用来存储最大子段和
	if (left == right)	//只有一个元素
	{
		sum = a[left] > 0 ? a[left] : 0;
	}
	else
	{
		int center = (left + right)/2;
		int leftsum = MaxSubSum(a,left,center);
		int rightsum = MaxSubSum(a,center+1,right);

		//下面是第三种情况
		int s1 = 0,lefts = 0;
		for (int i = center; i >= left; i --)
		{
			lefts += a[i];
			if (lefts > s1)
				s1 = lefts;
		}

		int s2 = 0,rights = 0;
		for (i = center+1; i <= right; i ++)
		{
			rights += a[i];
			if (rights > s2)
				s2 = rights;
		}

		sum = s1 + s2;
		if (sum < leftsum)
			sum = leftsum;
		if (sum < rightsum)
			sum = rightsum;
	}
	return sum;
}