最大子序列和問題之算法優化

算法一：窮舉式地嘗試所有的可能

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幾乎是完美的算法。

————《數據結構與算法分析》（中文版第二版）

數據結構與算法分析：C語言描述（原書第2版） PDF+源代碼+習題答案 下載見 http://www.linuxidc.com/Linux/2014-04/99735.htm