学步园

题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1,
-2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。

要求最大的子数组的和．我们可以想象，当遍历到其中一个数A[i],如果A[i]之前的数组之和CurrentSum ＝> 0,那么CurrentSum+A[i]＝>A[i]，那么最大值就应该在CurrentSum+A[i]和CurrentSum中取，因为A[i]有可能是正数也有可能是负数．因此用Sum来记录最终的最大值Sum=max(CurrentSum+A[i],CurrentSum),如果CurrentSum
<　0,则有CurrentSum+A[i] < A[i],所以，应该舍弃CurrentSum，用A[i]更新CurrentSum.

代码：

#include<iostream>
#include<Limits.h>
using namespace std;
int MaxArray(int* A,int n)
{
	int Sum=INT_MIN;
	int CurrentSum=0;
	for(int i=0;i<n;++i)
	{
		if(CurrentSum < 0)//如果i之前的和为负，则抛弃前边的，从A[i]开始统计新的和
			CurrentSum = A[i];
		else			//如果i之前的为正，则继续累加
			CurrentSum += A[i];
		if(Sum < CurrentSum)
			Sum=CurrentSum;
	}
	return Sum;
}
void main()
{
	int A[]={ -2,11, 11, 9, -7, -2, -5,-1};
	int len=sizeof(A)/sizeof(A[0]);
	cout<<MaxArray(A,len);
}