连续子数组的最大和_一个数组有多少个子数组

题目：输入一个整型数组，数组中有正数也有负数。数组中有一个或者连续的多个整数组组成一个子数组。求所有的子数组的和的最大值。要求时间复杂度为O(n)。

分析：例如输入的数组为{}1，-2,3,10，-4,7,2，-5}，和最大子数组为{3,10，-4,7,2}，因此输出为该子数组的和18。最直观的解法就是枚举出数组的所有子数组并求出它们的和。一个长度为n的数组，总共有n(n-1)/2个子数组。计算出所有的子数组的和，最快也要O（n^2）时间。

测试用例：

功能测试（输入的数组中全是正数，全是负数，正数负数都有）

特殊输入测试（表示数组的指针为NULL指针）

解法：应用动态规划

如果用f(i)表示以第i个数字结尾的子数组的最大和，那么我们需要求出max[f(i)]，0<=i<n,我们可以用递归公式求出f(i)；

这个公式的意义：当以第i-1个数字结尾的子数组所有数字的和小于0时，如果把这个负数和第i个数累加，得到结果比第i个数字本身还要小，所以这种情况小以第i个数字结尾的子数组就是第i个数字本身，如果第i-1个数字结尾的子数组所有数字的和大于0，与第i个数字累加就可以得到以第i个数字结尾的子数组中的所有数字的和

代码：

bool g_InvalidInput=false;
void FindGreatestSumOfSubArray(int* pdata,int nLength)
{
	if(pdata==NULL || nLength<=0)
	{
		g_InvalidInput=true;
		return;
	}
	g_InvalidInput=false;	
	int currSum=0;
	int GreatestSum=0;
	for(int i=1;i<nLength;i++)
	{
		if(currSum<=0)
			currSum=pdata[i];
		else
		{
			currSum+=pdata[i]
		}
		if(currSum>GreatestSum)
			GreatestSum=currSum;
			
	}
	return GreatestSum;
}