走刀口

问题：

给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整均为负数时定义子段和为0，依此定义，所求的最优值为：

Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如，当（a1,a2,a3,a4,a4,a6）=(-2,11,-4,13,-5,-2)时，最大子段和为20 下面列出了四种计算方式，时间复杂度各逐渐变小，其中动态规划法时间复杂度最小。

/**
 * @brief 最大子段和，穷举法，时间复杂度O(n^3)
 *
 */
int MaxSum(int* A, int n)
{
	int sum = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = i; j < n; ++j)
		{
			int thissum = 0;
			for (int k = i; k <= j; ++k)
			{
				thissum += A[k];
			}
			if (thissum > sum)
			{
				sum = thissum;
			}
		}
	}
	return sum;
}
/**
 * @brief 最大子段和，穷举法改进，时间复杂度O(n^2)
 *
 */
int MaxSumEx(int* A, int n)
{
	int sum = 0;
	for (int i = 0; i < n; ++i)
	{
		int thissum = 0;
		for (int j = i; j < n; ++j)
		{
			thissum += A[j];
			if (thissum > sum)
			{
				sum = thissum;
			}
		}
	}
	return sum;
}
/**
 * @brief 最大子段和，分治法，时间复杂度O(nlogn)
 *
 * 将a[1n]分成a[1n/2]和a[n/2+1n],则a[1n]的最大字段和有三种情况:
 * (1)a[1n]的最大子段和与a[1n/2]的最大子段和相同
 * (2)a[1n]的最大子段和与a[n/2n]的最大子段和相同
 * (3)a[1n]的最大子段和为ai++aj,1<=i<=n/2,n/2+1<=j<=n
 * T(n)=2T(n/2)+O(n)
 * T(n)=O(nlogn)
 */
int MaxSum_DIV(int* A, int left, int right)
{
	int sum = 0;
	if (left == right)
	{
		sum = A[left] > 0 ? A[left] : 0;
	}
	else
	{
		int center = (left + right) / 2;
		int leftMax = MaxSum_DIV(A, left, center);
		int rightMax = MaxSum_DIV(A, center + 1, right);

		int s1 = 0, leftSum = 0;
		for (int i = center; i >= left; --i)
		{
			leftSum += A[i];
			if (leftSum > s1)
			{
				s1 = leftSum;
			}
		}
		int s2 = 0, rightSum = 0;
		for (int j = center + 1; j <= right; ++j)
		{
			rightSum += A[j];
			if (rightSum > s2)
			{
				s2 = rightSum;
			}
		}

		sum = s1 + s2;
		if (leftMax > sum)
		{
			sum = leftMax;
		}
		if (rightMax > sum)
		{
			sum = rightMax;
		}
	}
	return sum;
}
/* @brief 最大子段和，动态规划法，时间复杂度O(n)
 * b[j]=max{a[i]++a[j]},1<=i<=j,且1<=j<=n,则所求的最大子段和为max b[j]，1<=j<=n。
 * 由b[j]的定义可易知，当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。故b[j]的动态规划递归式为:
 * b[j]=max(b[j-1]+a[j],a[j])，1<=j<=n。
 * T(n)=O(n)
 */
int MaxSum_DYN(int* A, int n)
{
	int sum = 0;
	int b = 0;
	for (int i = 0; i < n; ++i)
	{
		if (b > 0)
		{
			b += A[i];
		}
		else
		{
			b = A[i];
		}
		if (b > sum)
		{
			sum = b;
		}
	}
	return sum;
}

int main()
{
	int A[6] = {-2,11,-4,13,-5,-2};
	cout << MaxSum(A, 6) << endl;
	cout << MaxSumEx(A, 6) << endl;
	cout << MaxSum_DIV(A, 0, 5) << endl;
	cout << MaxSum_DYN(A, 6) << endl;
}