接续子数组的最大和

连续子数组的最大和

/*********************************************************************
题目：输入一个整型数组，数组里有整数也有负数。数组中一个或连续的多个整数
组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(N)。
*********************************************************************/
#include<iostream>
using namespace std;

int greatestSumOfSubArray(int* arr, int length)
{
	if(arr == NULL || length<=0)
		throw exception("Invalid input!\n");

	int sum = arr[0];
	int greatestSum = arr[0];

	for(int i=0; i<length; ++i)
	{
		if(sum <= 0)
			sum = arr[i];
		else
			sum += arr[i];
		if(sum > greatestSum)
			greatestSum = sum;
	}
	return greatestSum;
}

void test()
{
	int arr[8] = {1,-2,3,10,-4,7,2,-5};
	cout << greatestSumOfSubArray(arr,8) << endl;

}
void test1()
{
	cout << greatestSumOfSubArray(NULL,0) << endl;

}
int main()
{
	try{
		test();
		test1();
	}
	catch(exception ex)
	{
		cout << ex.what()<<endl;
	}
	return 0;
}
//时间复杂度为O(N)

==参考剑指offer