最大子序列和问题之算法优化

算法一：穷举式地尝试所有的可能

int maxSubsequenceSum(const int a[], int n)
{
	int i, j, k;
	int thisSum, 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;
}

算法复杂度为O(n^3)（三重for循环）

算法二：算法一的改进

int maxSubsequenceSum(const int a[], int n)
{
	int i, j;
	int thisSum, 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;
}

该算法去除了算法一中不必要的计算，时间复杂度为O(n^2)（两重for循环）。

算法三：分治（divide-and-conquer）策略

分治策略：

分：把问题分成若干个（通常是两个）规模相当的子问题，然后递归地对它们求解。

治：将若干个问题的解4合并到一起并可能再做少量的附加工作，最后得到整个问题的解。

在这个问题中，最大子序列和可能在三处出现：即左半部序列、右半部序列、穿过中部从而占据左右两半部分的序列。前两种情况可以通过递归求解。而递归的基准情况（base cases）是序列只有一个元素（left == right），若该元素大于0，则返回该元素，否则返回0。第三种情况的最大和可以通过分别求出左边部分（包含左半部分最后一个）的最大和以及右边部分（包含右边部分的第一个）的最大和，再将它们相加得到。

int maxSubsequenceSum(const int a[], int left, int right)
{
	int i, mid, maxLeftSum, maxRightSum;
	int maxLeftBorderSum, leftBorderSum;
	int maxRightBorderSum, rightBorderSum;

	if (left == right) {            /*基准情况*/
    	if (a[left] >= 0)
    	    return a[left];
    	else
    	    return 0;
	}
	mid = left + (right - left) / 2;
	maxLeftSum = maxSubsequenceSum(a, left, mid);       /*左半部分的最大和*/
	maxRightSum = maxSubsequenceSum(a, mid+1, right);   /*右半部分的最大和*/
	/*下面求穿过中点的最大和*/
	maxLeftBorderSum = 0, leftBorderSum = 0;
	for (i = mid; i >= left; i--)       /*中点及其以左的最大和*/
	{
    	leftBorderSum += a[i];
    	if (leftBorderSum > maxLeftBorderSum)
    	    maxLeftBorderSum = leftBorderSum;
	}
	maxRightBorderSum = 0, rightBorderSum = 0;
	for (i = mid+1; i <= right; i++)   /*中点以右的最大和*/
	{
	    rightBorderSum += a[i];
	    if (rightBorderSum > maxRightBorderSum)
	        maxRightBorderSum = rightBorderSum;
	}
	/*返回三部分中的最大值*/
	return max3(maxLeftSum, maxRightSum, maxLeftBorderSum+maxRightBorderSum);
}

int max3(int a, int b, int c)
{
	int maxNum  = a;

	if (b > maxNum)
	    maxNum = b;
	if (c > maxNum)
	    maxNum = c;
	return maxNum;
}

以序列2，4，-1，-5，4，-1为例，其左半部分最大和为2 + 4 = 6；右半部分最大和为4，穿过中心的最大和为（-1 + 4 + 2）+ （-5 + 4）= 0。故该序列的最大子序列和为max（6，4，0）= 6。

时间复杂度分析: 假设T(n)为求解大小为n的最大子序列和问题所花费的时间。当n = 1是，T(1) = O(1)；当n > 1时，两次递归花费的总时间为2T(n/2),两个并列的for循环花费的时间是O(len(left)+len(right)) = O(n)，一共为2T(n/2)+O(n)。综上可列如下方程组：

事实上，上述方程组常常通用于分治算法，由方程组可算出T(n) = O(nlogn)。

算法四：

算法三利用递归较好的解决了最大子序列和问题，但仔细分析，在递归过程中，同一个元素很可能多次被操作，有没有更高效的算法？先上代码！

int maxSubsequenceSum(const int a[], int n)
{
	int i;
	int maxSum, thisSum;
	maxSum = thisSum = 0;
	for (i = 0; i < n; i++)
	{
	    thisSum += a[i];
	    if (thisSum > maxSum)
	        maxSum = thisSum;
	    else if (thisSum < 0)
	        thisSum = 0;
	}
	return maxSum;
}

可以简单的分析出上述代码的时间复杂度是O(n),比前三种都高效。它为什么是正确的？从直观上理解：首先for循环的if语句保证了每次更新后最大和保存在maxSum中，而我们从i = 0开始扫描，假设扫描到i = t(t < n)，且此时的最大和已经保存在maxSum中，而当前的和（thisSum）如果大于0，不管当i > t的元素大小如何，加上thisSum总会使之后的和变大，而如果thisSum小于0，肯定会使之后的和变小
，既然还会变小，那干脆就重新来过（thisSum = 0），有些另起炉灶的意味。

该算法一个附带的优点是，它只对数据进行一次的扫描，一旦a[i]被读入并被处理，它就不再需要记忆。因此，如果数组在磁盘或磁带上，它就可以被顺序读入，在主存中不必储存数组的任何部分。不仅如此，在任意时刻，该算法都能对它已经读入的数据给出子序列问题的正确答案（其他算法即前三种不具有这个特性）。具有这种特性的算法叫做联机算法（online algorithm）。仅需要常量空间并以线性时间运行的online algorithm几乎是完美的算法。

————《数据结构与算法分析》（中文版第二版）