Maximum subarray problem

maxSubarray.cpp

//http://poj.org/problem?id=1050
//http://poj.org/problem?id=2479
//shihongzhi --2012.3.8

#include <stdio.h>

int maxSubarray(int *A, int n)
{
	int max = 0;
	int sum = 0;
	int begin, end;
	for (int i=0; i<n; ++i)
	{
		if (sum <= 0)
		{
			sum = A[i];
			begin = i;
		}
		else
			sum += A[i];
		if (sum > max)
		{
			max = sum;
			end = i;
		}
	}
	return max;
}

int main()
{
	int test[] = {-2,1,-3,4,-1,2,1,-5,4};
	printf("%d\n", maxSubarray(test, 9));
	return 0;
}