最大子序列和

《算法导论》第三版讲分治时引用了一个很好的例子，股票的涨幅。
而其本质是与《数据结构与算法分析》的开篇一样的，最大子序列和问题。

问题描述：已知每天股票的价格，选择一个买入点和一个抛出点，使得获取利润最大。

问题转换：一个整数序列 A[N](可能有负)，求 A[i] 加到 A[j] 的最大值(0 <= i <= j < N)。如果所有整数均为负数，那么最大子序列和为0。
数组A表示的就是今天股票与昨天的差价。

一、首先会想到，可以用两个循环搞定，O(n^2)。

二、分治，O(nlogn)，copy一下

int maxSubsequenceSum(int A[], int left, int right)
{
	int maxLeftSum, maxRightSum;
	int maxLeftBorderSum, maxRightBorderSum;
	int leftBorderSum, rightBorderSum;
	int mid, i;
	
	if (left == right)	// base case
		if (A[left] > 0)
			return A[left];
		else
			return 0;
	
	mid = (left + right)/2;
	maxLeftSum = maxSubsequenceSum(A, left, mid);
	maxRightSum = maxSubsequenceSum(A, mid+1, right);
	
	maxLeftBorderSum = leftBorderSum = 0;
	for (i = mid; i >= left; i--) {
		leftBorderSum += A[i];
		if (leftBorderSum > maxLeftBorderSum)
			maxLeftBorderSum = leftBorderSum;
	}
	
	maxRightBorderSum = rightBorderSum = 0;
	for (i = mid + 1; i <= right; i++) {
		rightBorderSum += A[i];
		if (rightBorderSum > maxRightBorderSum)
			maxRightBorderSum = rightBorderSum;
	}
	
	return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
}

三、Aha！灵机一动，O(n)

int maxSubsequenceSum(int A[], int left, int right)
{
	int thisSum, maxSum, i;
	
	thisSum = maxSum = 0;
	for (i = left; i <= right; i++) {
		thisSum += A[i];
		
		if (thisSum < 0)
			thisSum = 0;
		else if (thisSum > maxSum)
			maxSum = thisSum;
	}
	return maxSum;
}