浙江大學-數據結構-應用實例：最大子列和問題-1.3

03-03

第一次在知乎寫文章...就當寫些筆記吧。

數據結構是陳越姥姥上的，姥姥講課思路特別清晰，聽著...不容易累。有興趣的可以關注陳越老師的知乎賬號"陳越姥姥"。

如何在一個整數序列中找出最大的子列和，談談四種演算法，四種演算法我都放在PTA里測試了一遍，兩種呆瓜演算法都會有測試點被卡。

1、呆瓜演算法（1）

#include <stdio.h>int a[100000];int maxsubseqsum(int a[], int n){ int thissum = 0, 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;}int main(int argc, const char * argv[]) { int n; scanf("%d",&n); for(int i = 0; i<n; i++){ scanf("%d",&a[i]); } printf("%d ",maxsubseqsum(a,n)); return 0;}

三層循環一一遍歷來更新子列和的最大值，效率非常低下，在PTA的測試數據中可以看出當測試的數組元素為10000時就會出現TLE（運行超時）的錯誤。畢竟10000的三次方已經變成極為龐大的數

時間複雜度：T(n) = O(n^3)

2、呆瓜演算法（2）

#include <stdio.h>int a[100000];int maxsubseqsum(int a[], int n){ int thissum = 0, 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;}int main(int argc, const char * argv[]) { int n; scanf("%d",&n); for(int i = 0; i<n; i++){ scanf("%d ",&a[i]); } printf("%d",maxsubseqsum(a,n)); return 0;}

如果讓我寫這道題的話，我可能第一時間寫出來的是這種演算法，兩重循環的遍歷來搜索，，思路非常簡潔明了，對第一種演算法進行了優化，雖然比第一種演算法好出整整一個數量級，但是依然是不夠的，在PTA的測試數據中我們也可以看出，當測試數據的數組元素為100000時就會出現TLE（運行超時）的錯誤。

時間複雜度：T(n) = O(n^2)

3、分治演算法

#include <stdio.h>int a[100000];int Max3( int A, int B, int C ){ /* 返回3個整數中的最大值 */ return A > B ? A > C ? A : C : B > C ? B : C;}int DivideAndConquer( int List[], int left, int right ){ /* 分治法求List[left]到List[right]的最大子列和 */ int MaxLeftSum, MaxRightSum; /* 存放左右子問題的解 */ int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界線的結果*/ int LeftBorderSum, RightBorderSum; int center, i; if( left == right ) { /* 遞歸的終止條件，子列只有1個數字 */ if( List[left] > 0 ) return List[left]; else return 0; } /* 下面是"分"的過程 */ center = ( left + right ) / 2; /* 找到中分點 */ /* 遞歸求得兩邊子列的最大和 */ MaxLeftSum = DivideAndConquer( List, left, center ); MaxRightSum = DivideAndConquer( List, center+1, right ); /* 下面求跨分界線的最大子列和 */ 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 > MaxRightBorderSum ) MaxRightBorderSum = RightBorderSum; } /* 右邊掃描結束 */ /* 下面返回"治"的結果 */ return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );}int MaxSubseqSum3( int List[], int N ){ /* 保持與前2種演算法相同的函數介面 */ return DivideAndConquer( List, 0, N-1 );}int main(int argc, const char * argv[]) { int n; scanf("%d",&n); for(int i = 0; i<n; i++){ scanf("%d",&a[i]); } printf("%d",DivideAndConquer(a,0,n-1)); return 0;}

姥姥的解法中用到了大名鼎鼎的分治演算法，之前在快速排序中有遇到過，知道現在仍然不是很會用，這裡的代碼完全是帖姥姥的。效率非常高的演算法，順利通過了PTA中的所有測試數據。

時間複雜度：T(n) = O(nlogn)

4、在線處理

#include <stdio.h>int a[100000];int maxsubseqsum(int a[], int n){ int thissum = 0, maxsum = 0; int i; for(i = 0; i<n; i++){ thissum += a[i]; if(thissum > maxsum) maxsum = thissum; //發現和的最大值將其值賦值給maxsum else if(thissum < 0) thissum = 0; /*若子列和小於零，就將其丟棄，因為小於零的子列不可能使後面部分和增大*/ } return maxsum;}int main(int argc, const char * argv[]) { int n; scanf("%d",&n); for(int i = 0; i<n; i++){ scanf("%d",&a[i]); } printf("%d",maxsubseqsum(a,n)); return 0;}

在考慮的時候有隱隱朝這個方向思考，加以時間也能想出這種方法，比較巧妙且極為高效的演算法，只需要將所有數據掃描一遍即可，已經達到最優情況，非常快地通過了PTA中所有測試數據。

時間複雜度：T(n) = O(n)

還是小白歡迎大牛指出錯誤或提出更優演算法??