數(shù)據(jù)結(jié)構(gòu)與算法分析:最大子序列和問題之算法優(yōu)化

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

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;}

算法復(fù)雜度為O(n^3)（三重for循環(huán)）

算法二：算法一的改進(jìn)

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;}

該算法去除了算法一中不必要的計(jì)算，時間復(fù)雜度為O(n^2)（兩重for循環(huán)）。

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

分治策略：

分：把問題分成若干個（通常是兩個）規(guī)模相當(dāng)?shù)淖訂栴}，然后遞歸地對它們求解。

治：將若干個問題的解4合并到一起并可能再做少量的附加工作，最后得到整個問題的解。

在這個問題中，最大子序列和可能在三處出現(xiàn)：即左半部序列、右半部序列、穿過中部從而占據(jù)左右兩半部分的序列。前兩種情況可以通過遞歸求解。而遞歸的基準(zhǔn)情況（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) { /*基準(zhǔn)情況*/

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); /*右半部分的最大和*/

/*下面求穿過中點(diǎn)的最大和*/

maxLeftBorderSum = 0, leftBorderSum = 0;

for (i = mid; i >= left; i--)

/*中點(diǎn)及其以左的最大和*/

{

leftBorderSum += a[i];

if (leftBorderSum > maxLeftBorderSum)

maxLeftBorderSum = leftBorderSum;

}

maxRightBorderSum = 0, rightBorderSum = 0;

for (i = mid+1; i <= right; i++) ? /*中點(diǎn)以右的最大和*/?

{

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。時間復(fù)雜度分析:假設(shè)T(n)為求解大小為n的最大子序列和問題所花費(fèi)的時間。當(dāng)n = 1是，T(1) = O(1)；當(dāng)n > 1時，兩次遞歸花費(fèi)的總時間為2T(n/2),兩個并列的for循環(huán)花費(fèi)的時間是O(len(left)+len(right)) = O(n)，一共為2T(n/2)+O(n)。綜上可列如下方程組：

T(1) = 1T(n) = 2T(n/2) + O(n)

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

算法四：

算法三利用遞歸較好的解決了最大子序列和問題，但仔細(xì)分析，在遞歸過程中，同一個元素很可能多次被操作，有沒有更高效的算法？先上代碼

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;?}

可以簡單的分析出上述代碼的時間復(fù)雜度是O(n),比前三種都高效。它為什么是正確的？從直觀上理解：首先for循環(huán)的if語句保證了每次更新后最大和保存在maxSum中，而我們從i = 0開始掃描，假設(shè)掃描到i = t(t < n)，且此時的最大和已經(jīng)保存在maxSum中，而當(dāng)前的和（thisSum）如果大于0，不管當(dāng)i > t的元素大小如何，加上thisSum總會使之后的和變大，而如果thisSum小于0，肯定會使之后的和變小，既然還會變小，那干脆就重新來過（thisSum = 0），有些另起爐灶的意味。

該算法一個附帶的優(yōu)點(diǎn)是，它只對數(shù)據(jù)進(jìn)行一次的掃描，一旦a[i]被讀入并被處理，它就不再需要記憶。因此，如果數(shù)組在磁盤或磁帶上，它就可以被順序讀入，在主存中不必儲存數(shù)組的任何部分。不僅如此，在任意時刻，該算法都能對它已經(jīng)讀入的數(shù)據(jù)給出子序列問題的正確答案（其他算法即前三種不具有這個特性）。具有這種特性的算法叫做聯(lián)機(jī)算法（online algorithm）。僅需要常量空間并以線性時間運(yùn)行的online algorithm幾乎是完美的算法?！稊?shù)據(jù)結(jié)構(gòu)與算法分析》（中文版第二版）