//****************************************************************************************************
//
//  求子数组的最大和 - C++ - by Chimomo
//
//  题目： 输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
//  例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5；和最大的子数组为3, 10, -4, 7, 2；因此输出为该子数组的和18。
//
//  Answer: A traditional greedy approach. Keep current sum, slide from left to right, when sum < 0, reset sum to 0.
//
//****************************************************************************************************

#include <iostream>
#include <stdio.h>

using namespace std;

int MaxSubArray(int a[], int size)
{
	if(size <= 0)
	{
		length_error("Error, wrong array size.");
	}

	int sum = 0;
	int max = -(1 << 31);
	int cur = 0;

	while(cur < size)
	{
		sum += a[cur++];

		if(sum > max)
		{
			max = sum;
		}
		else if(sum < 0)
		{
			sum = 0;
		}
	}

	return max;
} 


int main(int argc, char* argv[])
{
	int a[] = {1, -2, 3, 10, -4, 7, 2, -5};
	cout << MaxSubArray(a, 8) << endl;

	return 0;
}

// Output:
/*
18
*/

算法 - 求子数组的最大和（C++）,布布扣,bubuko.com

算法 - 求子数组的最大和（C++）