這是一道考的爛的不能再爛的題目，但是依然有很多公司樂于將這樣的題目作為筆試或面試題，足見其經典。

題目描述：

輸入一個整形數組，數組里有正數也有負數。 數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。 求所有子數組的和的最大值。要求時間復雜度為O(n)。例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數組為3, 10, -4, 7, 2， 因此輸出為該子數組的和18。

下面按照時間復雜度逐步優化的順序依次給出這三種算法。

暴力求解法

該方法的思想非常簡單，先找出從第1個元素開始的最大子數組，而后再從第2個元素開始找出從第2個元素開始的最大子數組，依次類推，比較得出最大的子數組。實現代碼如下：

/* 常規方法,時間復雜度O（n*n） 先從第一個元素開始向后累加， 每次累加后與之前的和比較，保留最大值， 再從第二個元素開始向后累加，以此類推。 */ int MaxSubSum1(int *arr,int len) {int i,j;int MaxSum = 0;//每次開始累加的起始位置的循環for(i=0;i<len;i++){int CurSum = 0;//向后累加的循環for(j=i;j<len;j++){CurSum += arr[j];if(CurSum > MaxSum)MaxSum = CurSum;}}return MaxSum; }

很明顯地可以看出，該方法的時間復雜度為O（n*n）。

分治求解法

解釋一

考慮將數組從中間分為兩個子數組，則最大子數組必然出現在以下三種情況之一：

1、完全位于左邊的數組中。2、完全位于右邊的數組中。3、跨越中點，包含左右數組中靠近中點的部分。遞歸將左右子數組再分別分成兩個數組，直到子數組中只含有一個元素，退出每層遞歸前，返回上面三種情況中的最大值。實現代碼如下： /* 求三個數中的最大值 */ int Max3(int a,int b,int c) {int Max = a;if(b > Max)Max = b;if(c > Max)Max = c;return Max; }/* 次優算法，采用分治策略 */ int MaxSubSum2(int *arr,int left,int right) {int MaxLeftSum,MaxRightSum; //左右邊的最大和int MaxLeftBorderSum,MaxRightBorderSum; //含中間邊界的左右部分最大和int LeftBorderSum,RightBorderSum; //含中間邊界的左右部分當前和int i,center;//遞歸到最后的基本情況if(left == right)if(arr[left]>0)return arr[left];elsereturn 0;//求含中間邊界的左右部分的最大值center = (left + right)/2;MaxLeftBorderSum = 0;LeftBorderSum = 0;for(i=center;i>=left;i--){LeftBorderSum += arr[i];if(LeftBorderSum > MaxLeftBorderSum)MaxLeftBorderSum = LeftBorderSum;}MaxRightBorderSum = 0;RightBorderSum = 0;for(i=center+1;i<=right;i++){RightBorderSum += arr[i];if(RightBorderSum > MaxRightBorderSum)MaxRightBorderSum = RightBorderSum;}//遞歸求左右部分最大值MaxLeftSum = MaxSubSum2(arr,left,center);MaxRightSum = MaxSubSum2(arr,center+1,right);//返回三者中的最大值return Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum); }/* 將分支策略實現的算法封裝起來 */ int MaxSubSum2_1(int *arr,int len) {return MaxSubSum2(arr,0,len-1); }

設該算法的時間復雜度為T（n）,則：

T（n）= 2T（n/2）+ O（n），且T（1）= 1。

逐步遞推得到時間復雜度T（n）= O（nlogn）。

---

另一種通俗解釋二

這里再介紹一種更高效的算法，時間復雜度為O(nlogn)。這是個分治的思想，解決復雜問題我們經常使用的一種思維方法——分而治之。
而對于此題，我們把數組A[1..n]分成兩個相等大小的塊：

A[1..n/2]和A[n/2+1..n]，最大的子數組只可能出現在三種情況：A[1..n]的最大子數組和A[1..n/2]最大子數組相同； A[1..n]的最大子數組和A[n/2+1..n]最大子數組相同； A[1..n]的最大子數組跨過A[1..n/2]和A[n/2+1..n]

前兩種情況的求法和整體的求法是一樣的，因此遞歸求得。

第三種，我們可以采取的方法也比較簡單，沿著第n/2向左搜索，直到左邊界，找到最大的和maxleft，以及沿著第n/2+1向右搜索找到最大和maxright，那么總的最大和就是maxleft+maxright。而數組A的最大子數組和就是這三種情況中最大的一個。

偽代碼

int maxSubArray(int *A,int l,int r) {if l<r do mid = (l+r)/2;ml = maxSubArray(A,l,mid); //分治 mr = maxSubArray(A,mid+1,r);for i=mid downto l do search maxleft; for i=mid+1 to r do search maxright; return max(ml,mr,maxleft+maxright); //歸并 then //遞歸出口 return A[l]; }

---

線性時間算法

該算法在每次元素累加和小于0時，從下一個元素重新開始累加。實現代碼如下：

/* 最優方法，時間復雜度O（n） 和最大的子序列的第一個元素肯定是正數 因為元素有正有負，因此子序列的最大和一定大于0 */ int MaxSubSum3(int *arr,int len) {int i;int MaxSum = 0;int CurSum = 0;for(i=0;i<len;i++){CurSum += arr[i];if(CurSum > MaxSum)MaxSum = CurSum;//如果累加和出現小于0的情況，//則和最大的子序列肯定不可能包含前面的元素，//這時將累加和置0，從下個元素重新開始累加if(CurSum < 0)CurSum = 0;}return MaxSum; }

顯然，該算法的時間復雜度O（n）。該算法理解起來應該不難，但是要想出來可就不容易了。另外，該算法的一個附帶的有點是：它只對數據進行一次掃描，一旦元素被讀入并被處理，它就不再需要被記憶。因此，如果數組在磁盤或磁帶上，他就可以被順序讀入，在主存中不必存儲數組的任何部分。不僅如此，在任意時刻，該算法都能對它已經讀入的數據給出最大子數組（另外兩種算法不具有這種特性）。具有這種特性的算法叫做聯機算法。

掃描法

掃描算法實際上就是上面的線性時間算法，這里是轉載的自另一個作者，思路邏輯可能更加嚴謹一些，分析也更加精確。

當我們加上一個正數時，和會增加；當我們加上一個負數時，和會減少。如果當前得到的和是個負數，那么這個和在接下來的累加中應該拋棄并重新清零，不然的話這個負數將會減少接下來的和。實現：

（后加注：這里提到的掃描法存在一個問題就是如果最大字段和小于0則算法沒法給出正確答案。其實這個問題用動態規劃就好，這里的掃描法其實真的不是個好方法，只是因為很有名所以還是粘出來了）

//copyright@ July 2010/10/18 //updated，2011.05.25. #include <iostream.h> int maxSum(int* a, int n) { int sum=0; //其實要處理全是負數的情況，很簡單，如稍后下面第3點所見，直接把這句改成："int sum=a[0]"即可 //也可以不改，當全是負數的情況，直接返回0，也不見得不行。 int b=0; for(int i=0; i<n; i++) { if(b<0) //... b=a[i]; else b+=a[i]; if(sum<b) sum=b; } return sum; } int main() { int a[10]={1, -2, 3, 10, -4, 7, 2, -5}; //int a[]={-1,-2,-3,-4}; //測試全是負數的用例 cout<<maxSum(a,8)<<endl; return 0; } /*------------------------------------- 解釋下： 例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5， 那么最大的子數組為3, 10, -4, 7, 2， 因此輸出為該子數組的和18。 所有的東西都在以下倆行， 即： b ： 0 1 -1 3 13 9 16 18 13 sum： 0 1 1 3 13 13 16 18 18 其實算法很簡單，當前面的幾個數，加起來后，b<0后， 把b重新賦值，置為下一個元素，b=a[i]。 當b>sum，則更新sum=b; 若b<sum，則sum保持原值，不更新。。July、10/31。

（后加注：前面的代碼是粘貼別人的，下面的證明是我自己鼓搗的。之后由于看到了動態規劃法，覺得這個證明實在是沒什么必要看了。在后來練習了很多數學證明發現，證明是越精煉越好，不過這種敢于窮舉情況的思路還是很好的，很多時候難的證明題只要多窮舉幾種情況再加以精煉往往就能做出，大不了多舉幾個情況問題也能解決）

據說這道題是《編程珠機》里面的題目，叫做掃描法，速度最快，掃描一次就求出結果，復雜度是O（n）。書中說，這個算法是一個統計學家提出的。

這個算法如此精煉簡單，而且復雜度只有線性。但是我想，能想出來卻非常困難，而且證明也不簡單。在這里，我斗膽寫出自己證明的想法：

關于這道題的證明，我的思路是去證明這樣的掃描法包含了所有n^2種情況，即所有未顯示列出的子數組都可以在本題的掃描過程中被拋棄。

1 首先，假設算法掃描到某個地方時，始終未出現加和小于等于0的情況。

我們可以把所有子數組（實際上為當前掃描過的元素所組成的子數組）列為三種：

1.1 以開頭元素為開頭，結尾為任一的子數組

1.2 以結尾元素為結尾，開頭為任一的子數組

1.3 開頭和結尾都不等于當前開頭結尾的所有子數組

1.1由于遍歷過程中已經掃描，所以算法已經考慮了。1.2確實沒考慮，但我們隨便找到1.2中的某一個數組，可知，從開頭元素到這個1.2中的數組的加和大于0（因為如果小于0就說明掃描過程中遇到小于0的情況，不包括在大前提1之內），那么這個和一定小于從開頭到這個1.2數組結尾的和。故此種情況可舍棄

1.3 可以以1.2同樣的方法證明，因為我們的結尾已經列舉了所有的情況，那么每一種情況和1.2是相同的，故也可以舍棄。

2 如果當前加和出現小于等于0的情況，且是第一次出現，可知前面所有的情況加和都不為0

一個很直觀的結論是，如果子段和小于0，我們可以拋棄，但問題是是不是他的所有以此子段結尾為結尾而開頭任意的子段也需要拋棄呢？

答案是肯定的。因為以此子段開頭為開頭而結尾任意的子段加和都大于0（情況2的前提），所以這些子段的和是小于當前子段的，也就是小于0的，對于后面也是需要拋棄的。也就是說，所有以之前的所有元素為開頭而以當前結尾之后元素為結尾的數組都可以拋棄了。

而對于后面拋棄后的數組，則可以同樣遞歸地用1 2兩個大情況進行分析，于是得證。

這個算法的證明有些復雜，現在感覺應該不會錯，至少思路是對的，誰幫著在表達上優化下吧。:-)

動態規劃

設sum[i]為以第i個元素結尾且和最大的連續子數組。假設對于元素i，所有以它前面的元素結尾的子數組的長度都已經求得，那么以第i個元素結尾且和最大的連續子數組實際上，要么是以第i-1個元素結尾且和最大的連續子數組加上這個元素，要么是只包含第i個元素，即sum[i] = max(sum[i-1] + a[i], a[i])。可以通過判斷sum[i-1] + a[i]是否大于a[i]來做選擇，而這實際上等價于判斷sum[i-1]是否大于0。由于每次運算只需要前一次的結果，因此并不需要像普通的動態規劃那樣保留之前所有的計算結果，只需要保留上一次的即可，因此算法的時間和空間復雜度都很小。

偽代碼

result = a[1] sum = a[1]for i: 2 to LENGTH[a]if sum > 0sum += a[i]elsesum = a[i]if sum > resultresult = sumreturn result

---

參考文章地址1：http://www.cnblogs.com/waytofall/archive/2012/04/10/2439820.html

參考文章地址2：http://www.cnblogs.com/xkfz007/archive/2012/05/17/2506299.html

總結

以上是生活随笔為你收集整理的算法--三种方法求连续子数组的最大和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。