今天來討論一個很基礎(chǔ)的算法問題阅签，數(shù)列的最大子列和問題。這道題我是在看浙大陳姥姥的Mooc的時候看到的，算是陳越老師作為算法與數(shù)據(jù)結(jié)構(gòu)開篇講解的第一道算法實例題。
那么今天我就來記錄一下分析這道題的過程兄纺。
常用方法
首先，最大子列和這個問題有一個眾所周知的辦法化漆，即為每次從數(shù)列的開頭i，往結(jié)尾N累加钦奋，當(dāng)加至結(jié)尾時座云，由i+1再次累加疙赠，直到N-N。這樣的算法用三個變量三層循環(huán)來分別代表從頭至尾的遍歷朦拖，以及從i - N的前進(jìn)繼續(xù)累加圃阳，最后一層是累加的和。算法可以寫成下面這樣：
public static int MaxSubseqSum1(int[] A, int N) {
int ThisSum, MaxSum = 0;
int i, j, k;
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;
}
上面的第一種方法應(yīng)該非常好理解璧帝，而由于是三層循環(huán)捍岳，所以，這個算法的時間復(fù)雜度是T(N) = O(N^3)睬隶。這種時間復(fù)雜度的算法锣夹，是非常的低效的，并且我們作為一個有追求的程序員苏潜，看到一個時間復(fù)雜度上有平方以上指數(shù)的银萍，必須要考慮的是降次。
那么其實恤左，第一種算法贴唇，如果我們仔細(xì)思考，那么可以發(fā)現(xiàn)它最里面的一層飞袋，k循環(huán)是一個很愚蠢的行為戳气，因為我們可以直接在第二層循環(huán)里完成累加，于是巧鸭，我們可以寫一個稍微簡單的算法瓶您。
public static int MaxSubseqSum2(int[] A, int N) {
int ThisSum;
int MaxSum = 0;
int i, j;
for (i = 0; i < N; i++) {
ThisSum = 0;
for (j = i; j < N; j++) {
ThisSum += A[j];
if (ThisSum > MaxSum) {
MaxSum = ThisSum;
}
}
}
return MaxSum;
}
而這個去了一個循環(huán)的算法，時間復(fù)雜度也一目了然蹄皱，T(N) = O(N^2),但是時間復(fù)雜度依舊還有2次方览闰。接下來還有什么更好的辦法么？
分治法
在這里我們介紹一種方法叫分治法巷折，分而治之压鉴。這個方法的思想是，先把數(shù)列切割成左右兩個部分锻拘，接下來油吭，遞歸的把數(shù)列不斷切割為兩份，直到最小單位為一個元素署拟。而這時婉宰，分別去求他們的子列和，并且在求算左半邊和右半邊的子列和之后推穷，把跨越二分邊界的子列和也求解出來心包。比較左半邊的最大子列和，以及右半邊的最大子列和馒铃，以及跨越邊界的最大子列和蟹腾。取出最大的那個數(shù)痕惋，即為整個數(shù)列的最大子列和。
這是一種很常用的算法思想娃殖，可以先看代碼來理解一下值戳。
/**
* 分治法，保持API一致
* @param A 求解數(shù)列
* @param N 元素總數(shù)
* @return
*/
public static int MaxSubseqSum3(int[] A, int N) {
return DivideAndConquer(A, 0, N-1);
}
/**
* 分治法主體
* @param List 求解數(shù)列
* @param left 左半邊的下標(biāo)
* @param right 右半邊的下標(biāo)
* @return 所求數(shù)列的最大子列和
*/
public static int DivideAndConquer(int[] List, int left, int right) {
int MaxLeftSum, MaxRightSum;
int MaxLeftBorderSum, MaxRightBorderSum;
int LeftBorderSum, RightBorderSum;
int center, i;
if (left == right) {
if (List[left] > 0) {
return List[left];
} else {
return 0;
}
}
center = (left + right) / 2;
//分解數(shù)列 不斷遞歸調(diào)用
MaxLeftSum = DivideAndConquer(List, left, center);
MaxRightSum = DivideAndConquer(List, center + 1, right);
//分別結(jié)算左右兩邊的跨越邊界的和
MaxLeftBorderSum = 0; LeftBorderSum = 0;
for (i = center; i >= left; i--) {
LeftBorderSum += List[i];
if (LeftBorderSum > MaxLeftBorderSum) {
MaxLeftBorderSum = LeftBorderSum;
}
}
MaxRightBorderSum = 0; RightBorderSum = 0;
for (i = center + 1; i <= right; i++) {
RightBorderSum += List[i];
if (RightBorderSum > MaxLeftBorderSum) {
MaxRightBorderSum = RightBorderSum;
}
}
return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);
}
/**
* 取三個數(shù)中的最大值
* @return int
*/
private static int Max3(int A, int B, int C) {
return A > B ? A > C ? A : C : B > C ? B : C;
}
而分治法的時間復(fù)雜度炉爆，是
T(1) = O(1)
T (N) = 2T(N/2) + cN
= 2 [2T( N/22 ) + cN/2] + cN
= 2kO(1) + ckN
= O(NlogN )
現(xiàn)在我們可以看到堕虹，這個問題我們已經(jīng)完成我們的降次目標(biāo)了。那么還有更好的算法么芬首？
在線處理
這個問題有個最簡單的算法赴捞，叫在線處理法，遍歷數(shù)列的時候衩辟，順便累加螟炫，每次累加的和若是小于0，那么我們可以認(rèn)為最大子列和為負(fù)數(shù)時艺晴，一定不會讓后面的部分增大了昼钻，所以就可以把它丟棄，重新置當(dāng)前的sum = 0封寞。
代碼如下:
public static int MaxSubseqSum4(int[] A, int N) {
int ThisSum, MaxSum;
int i;
ThisSum = MaxSum = 0;
for (i = 0; i < N; i++) {
ThisSum += A[i];
if (ThisSum > MaxSum) {
MaxSum = ThisSum;
} else if (ThisSum < 0) {
ThisSum = 0;
}
}
return MaxSum;
}
在線處理的時間復(fù)雜度然评，因為是只遍歷一遍，所以為T(N) = O(N)狈究。
那么說了這么多碗淌，我們需要讓事實來說話，我們現(xiàn)在準(zhǔn)備一個30個元素的隊列抖锥，讓每個算法跑100000次來觀察所需時間亿眠。
public static void main(String[] args) {
int size = 31;
int[] testArr = {3, -1, 5, 10, -8, 2, 1, 4, 0, 7, -5, -6, 3, -8, -10,
10, -20, -8, 0, 3, 0, -9, -10, 5, 3, 0, -8, 10, -4, 10, -7};
int runCount = 100000;
testFunction1(testArr, size, runCount);
testFunction2(testArr, size, runCount);
testFunction3(testArr, size, runCount);
testFunction4(testArr, size, runCount);
}
最后的log輸出是這樣的:
Max Subsequence Sum 1 is 23
function1 run time is 738ms
Max Subsequence Sum 2 is 23
function2 run time is 44ms
Max Subsequence Sum 3 is 17
function3 run time is 110ms
Max Subsequence Sum 4 is 17
function4 run time is 54ms
上面的function的標(biāo)號，對應(yīng)上面的4種方法磅废，可以看到纳像，如果我們真的用了第一種笨辦法，那么他和高效算法之間的效率差距拯勉，實在是太大了竟趾。
算法的學(xué)習(xí)還要繼續(xù)，多看書宫峦，多做題岔帽。那么我們下次再分享了。
