延续子数组的最大和

连续子数组的最大和

问题描述：输入一个整数数组，数组中有正数也有负数，一个或连续的多个整数组成一个子数组，求所有子数组的和的最大值。

求子数组的和的最大值，首先可以求出数组所有子数组的和，再逐一比较可以得到和的最大值。这是最直观易懂的一种解法。但是对一个长度为n的数组，总共有n(n+1)/2个子数组，计算所有子数组的和时间复杂度为O(n^2)。而当n较大时，这种算法是很难被用户接受的。

对于数组(a1, a2, a3, ......, an)，设curSum为当前子数组(ai, ai+1, ......, aj)的和，其中1≤i<j<n，令k = j + 1且k ≤ n， sum = 0x80000000表示初始时子数组和的最大值。

1、如果curSum + ak > sum，那么sum = curSum + ak

2、如果curSum + ak ≤ 0，说明curSum已经是子数组(ai, ai+1, ......, aj, ak)的和的最大值, 那么curSum = ak，sum保持不变，对应的子数组为(ai, ai+1, ......, aj)

以数组{-1, -2, 3, 10, -4, 7, -2, -5}为例，初始时sum = 0x80000000, i = 0, curSum = 0

1)i = 0        curSum = -1        sum = -1 

2)i = 1        curSum = -2        sum = -1

3)i = 3        curSum = 3         sum = 3

4)i = 4        curSum = 13       sum = 13

5)i = 5        curSum = 9         sum = 13 

6)i = 6        curSum= 16        sum = 16

7)i = 7        curSum = 11        sum = 16 

有了上述思路，不难写出时间复杂度为O(n)的算法。

bool MaxSumOfSubArrays(int data[], int length, int &sum)
{
	if(data == NULL || length <= 0) // 数据输入合法性检验
		return false;

	sum = 0x80000000;   // 初始sum为最小32位有符号数
	int curSum = 0;
	for(int i = 0; i < length; ++i)
	{
		if(curSum <= 0)
			curSum = data[i];
		else
			curSum += data[i];
		
		if(curSum > sum)
			sum = curSum;
	}
	return true;
}