/*
*Author:	fdjiangwu
*Date:		2014.11.1
*Function:	给定整数A1，A2，...，AN(可能是负数)，求最大子序列的和，如果所有元素全是负数，认为是0
*Algorithm:	算法1和算法2略。算法3为递归算法，算法4技巧性强，需掌握递归算法
*/
#include <stdio.h>

int MaxSubsequenceSumUseAlgo1(const int A[], int N);
int MaxSubsequenceSumUseAlgo2(const int A[], int N);
int MaxSubsequenceSumUseAlgo3(const int A[], int N);
int MaxSubsequenceSumUseAlgo4(const int A[], int N);
static int MaxSubSum(const int A[], int Left, int Right);
static int MaxSubSum(const int A[], int Left, int Right);

int main()
{
	int A[] = {-2, 11, -4, 13, -5, -2};
	int arraynumber = sizeof(A) / sizeof(A[0]);
	int max1, max2, max3, max4;
	
	max1 = MaxSubsequenceSumUseAlgo1(A, arraynumber);
	max2 = MaxSubsequenceSumUseAlgo2(A, arraynumber);
	max3 = MaxSubsequenceSumUseAlgo3(A, arraynumber);
	max4 = MaxSubsequenceSumUseAlgo4(A, arraynumber);

	printf("%d, %d, %d, %d\n", max1, max2, max3, max4);

	return 0;
}

int MaxSubsequenceSumUseAlgo1(const int A[], int N)
{
	int ThisSum, MaxSum, i, j, k;

	MaxSum = 0;

	for(i = 0; i < N; i++)
		for(j = i; j < N; j++)
		{
			ThisSum = 0;
			for(k = i; k < j; k++)
				ThisSum += A[k];
			if(ThisSum > MaxSum)
				MaxSum = ThisSum;
		}
	return MaxSum;
}

int MaxSubsequenceSumUseAlgo2(const int A[], int N)
{
	int ThisSum, MaxSum, i, j;

	MaxSum = 0;

	for(i = 0; i < N; i++)
	{
		ThisSum = 0;
		for(j = i; j < N; j++)
		{
			ThisSum += A[j];
			if(ThisSum > MaxSum)
				MaxSum = ThisSum;
		}
	}
	
	return MaxSum;
}

static int Max3(int inta, int intb, int intc)
{
	int max = 0;
	max = (inta > intb) ? inta : intb;
	max = (max > intc) ? max : intc;

	return max;
}

static int MaxSubSum(const int A[], int Left, int Right)
{
	int MaxLeftSum, MaxRightSum;
	int MaxLeftBorderSum, MaxRightBorderSum;
	int LeftBorderSum, RightBorderSum;
	int Center, i;

	if(Left == Right)
	{
		return (A[Left] > 0) ? A[Left] : 0;
	}

	Center = (Left + Right) / 2;
	MaxLeftSum = MaxSubSum(A, Left, Center);
	MaxRightSum = MaxSubSum(A, Center + 1, Right);

	MaxLeftBorderSum = 0;
	LeftBorderSum = 0;
	for(i = Center; i >= Left; i--)
	{
		LeftBorderSum += A[i];
		if(LeftBorderSum > MaxLeftBorderSum)
			MaxLeftBorderSum = LeftBorderSum;
	}

	MaxRightBorderSum = 0;
	RightBorderSum = 0;
	for(i = Center + 1; i <= Right; i++)
	{
		RightBorderSum += A[i];
		if(RightBorderSum > MaxRightBorderSum)
			MaxRightBorderSum = RightBorderSum;
	}

	return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);
}

int MaxSubsequenceSumUseAlgo3(const int A[], int N)
{
	return MaxSubSum(A, 0, N - 1);
}

int MaxSubsequenceSumUseAlgo4(const int A[], int N)
{
	int ThisSum, MaxSum, j;
	ThisSum = MaxSum = 0;

	for(j = 0; j < N; j++)
	{
		ThisSum += A[j];
		if(ThisSum > MaxSum)
			MaxSum = ThisSum;
		else if(ThisSum < 0)
			ThisSum = 0;
	}

	return MaxSum;
}