??????? 題目：輸入一個整形數組，數組里有正數也有負數。數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。求所有子數組的和的最大值。要求時間復雜度為O(n)。

?????? 例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數組為3, 10, -4, 7, 2，因此輸出為該子數組的和18。

?????? 如果不考慮時間復雜度，我們可以枚舉出所有子數組并求出他們的和。不過非常遺憾的是，由于長度為n的數組有O(n2)個子數組；而且求一個長度為n的數組的和的時間復雜度為O(n)。因此這種思路的時間是O(n3)。

????? 很容易理解，當我們加上一個正數時，和會增加；當我們加上一個負數時，和會減少。如果當前得到的和是個負數，那么這個和在接下來的累加中應該拋棄并重新清零，不然的話這個負數將會減少接下來的和。基于這樣的思路，我們可以寫出如下代碼：?

/* // Find the greatest sum of all sub-arrays // Return value: if the input is valid, return true, otherwise return falseint *pData, // an array unsigned int nLength, // the length of array int &nGreatestSum // the greatest sum of all sub-arrays */ int start,end; bool FindGreatestSumOfSubArray(int *pData, unsigned int nLength, int &nGreatestSum) {// if the input is invalid, return falseif((pData == NULL) || (nLength == 0))return false;int k=0;int nCurSum = nGreatestSum = 0;for(unsigned int i = 0; i < nLength; ++i){nCurSum += pData[i];// if the current sum is negative, discard itif(nCurSum < 0){nCurSum = 0;k = i+1;}// if a greater sum is found, update the greatest sumif(nCurSum > nGreatestSum){nGreatestSum = nCurSum;start = k;end = i;}}// if all data are negative, find the greatest element in the arrayif(nGreatestSum == 0){nGreatestSum = pData[0];for(unsigned int i = 1; i < nLength; ++i){if(pData[i] > nGreatestSum){nGreatestSum = pData[i];start = end = i;}}}return true; }

?? 討論：上述代碼中有兩點值得和大家討論一下：

• ?函數的返回值不是子數組和的最大值，而是一個判斷輸入是否有效的標志。如果函數返回值的是子數組和的最大值，那么當輸入一個空指針是應該返回什么呢？返回0？那這個函數的用戶怎么區分輸入無效和子數組和的最大值剛好是0這兩中情況呢？基于這個考慮，本人認為把子數組和的最大值以引用的方式放到參數列表中，同時讓函數返回一個函數是否正常執行的標志。
• ?輸入有一類特殊情況需要特殊處理。當輸入數組中所有整數都是負數時，子數組和的最大值就是數組中的最大元素。

?方法二：編程之美2.14

/** ? 求最大子數組和（編程之美2.14，返回下標及首尾不相連） ** author :liuzhiwei? ? ** date?? :2011-08-17 起始點與結束點下標如何來記錄： 由于我要求起始點下標、結束點下標都靠前的子數組，所以我們在動態規劃的時候最好從后向前遞推，這樣dp[i]表示的值就是以下標i為開始的最大子數組的值，那么當dp[i]與dp[j]相同時我們選取i,j中較小的下標作為起點 **/ int maxSum(int *arr, int n, int & start, int & end) ? {int i , temp , dp , max ;dp = max = arr[n-1];start = end = n-1;temp = n-1;for(i = n - 2 ; i >= 0 ; --i){if(dp > 0)dp += arr[i];else{dp = arr[i];??? //拋棄當前子序列temp = i;??????? //開始新的子序列搜索}if(dp > max)??????? //更新最大子序列{max = dp;end = temp;start = i;?????????? //最大和增加，此時的i一定是最右端}}return max; } //特殊測試用例 -10 -1 -4

另外一種從前往后遍歷的方法如下：

// 需要保存起始點與結束點下標的時候，從前往后遍歷也是可以的 int MaxSum(int *a , int n) {int tempstart = 0 , sum=0 , max = -1000;int i , start , end;start = end = 0;for(i = 0 ; i < n ; ++i){if(sum < 0){sum = a[i];tempstart = i;}elsesum += a[i];if(sum > max){max = sum;start = tempstart;end = i;}}return max; }

拓展問題1：
如果認為數組是環形的，即首尾相接(下標n-1的元素后面的元素下標為0)，求最大子段和。
解析：
我覺得這個問題要比第一個問題容易，有很多種方法解決。我介紹三種方法，但是其中一種我覺得有問題，但卻作為《編程之美》這本書的一道練習答案，也可能是我理解錯作者的算法了，一會慢慢討論。
方法一：
這個問題的最優解一定是以下兩種可能。可能一：最優解沒有跨過a[n-1]到a[0]，即原問題，非環形數組?？赡芏?#xff1a;最優解跨過a[n-1]到a[0]，新問題。
對于第一種情況，我們可以按照簡單的動態規劃解法求得，設為max1；對于第二種情況，可以將原問題轉化為數組的最小子段和問題，再用數組全部元素的和減去最小子段和，那么結果一定是跨過a[n-1]到a[0]情況中最大的子段和，設為max2。最終結果即為max1與max2中較大的那個。
例1：有數組6、-1、-6、8、2
求得max1=10，max2=16，則取較大的max2作為結果。
例2：有數組-6、8、2、6、-1
求得max1=16，max2=15，則取較大的max1作為結果。
可能有些同學會對為什么：數組元素“sum - 最小子段和 = 跨過a[n-1]到a[0]情況中的最大子段和”這一點有些疑問。我們可以這樣理解：n個數的和是一定的，那么如果我們在這n個數中找到連續的一段數，并且這段數是所有連續的數的和最小的，那么“sum-最小子段和”的結果一定最大。故求得：跨過a[n-1]到a[0]情況中的最大子段和。
完整代碼如下：
//環形數組求最大子數組的和 int MaxSum(int *a , int n) {int i , sum , max1 , max2 , dp, min;dp = max1 = a[0];for(i = 1 ; i < n ; ++i) //最優解沒有跨過a[n-1]到a[0]，即原問題，非環形數組{if(dp < 0)dp = a[i];elsedp += a[i];if(dp > max1)max1 = dp;}sum = min = dp = a[0];for(i = 1 ; i < n ; ++i) //可以將原問題轉化為數組的最小子段和問題，再用數組全部元素的和減去最小子段和，那么結果一定是跨過a[n-1]到a[0]情況中最大的子段和{if(dp > 0)dp = a[i];elsedp += a[i];if(dp < min)min = dp;sum += a[i];}max2 = sum - min; //數組全部元素的和減去最小子段和return max1 > max2 ? max1 : max2;; //返回一個較大值 }第一部分即求第一種情況的最大值max1（用變量Max代替），第二部分中最初tmp為最小子段和，然后tmp值為sum-tmp；最后Max取兩者較大的數。
方法二：
方法二將問題轉化成另外一個問題：既然一段數的首尾可以相接，那么我們可以將數組復制，并接到自己的后面，然后我們求新數組的最大子數組的和，但這里要限制一個條件，就是最大子數組的長度不可以超過n。這樣我們就把問題轉化為拓展問題3了，我會在第三部分中介紹。
方法三：
方法三是《編程之美》這本書中介紹的，詳細見188頁，但是我覺得這種算法是錯誤的，可能是我理解作者的思路有問題，我將解法抄在下面，并舉出一個反例，有興趣討論的同學希望能給我留言。
摘自《編程之美》P188：
如果數組(A[0],A[1],A[2],......,A[n-1])首尾相鄰，也就是我們允許找到一段數字(A[i],A[i+1],......A[n-1],A[0],A[1],....,A[j])，使其和最大，怎么辦？
(1)解沒有跨過A[n-1] 到A[0] (原問題)。
(2)解跨過A[n-1]到A[0]。
對于第2種情況，只要找到從A[0]開始和最大的一段（A[0],…,A[j]）（0<=j<n），以及以A[n-1]結尾的和最大的一段（A[i],…,A[n-1]）（0<=i<n），那么，第2種情況中，和的最大值M_2為：
M_2=A[i]+…+A[n-1]+A[0]+…+A[j]
如果i <= j，則
M_2=A[0]+…+A[n-1]
否則
M_2=A[0]+…+A[j]+A[i]+…+A[n-1]
最后，再取兩種情況的最大值就可以了，求解跨過A[n-1]到A[0]的情況只需要遍歷數組一次，故總時間復雜度為O(N)+O(N)=O(N)。
解析：
分為兩種情況討論是沒有問題的，但是對于第2種情況的解法我認為是錯誤的，反例：
求5個元素的數組6,-1,-6,8,2的最大子數組和：M_1為10，但是如果利用上面的方法，M_2求得的結果為9，因為從A[0]開始和最大的一段即為A[0],…,A[n-1]為9，以A[n-1]結尾的和最大的一段（A[i],…,A[n-1]）為A[n-1]，由于這兩段有相交，故M_2= A[0]+…+A[n-1]。
最終結果為9，取兩種情況較大的，那么結果為10。但是正確結果明顯為16。
出現這種結果的原因：從A[0]開始和最大的一段雖然求的沒有錯，但是我們希望求得的結果并非是這一段，我們希望求得A[0]這一段，這樣就不會出現兩段相交的情況。
在第二部分中，我分析了兩個拓展問題，后面兩個拓展問題我會在第三部分中分析。
如果我上面有寫的不對的地方或者你有更好的方法，希望能提出來，互相學習嘛。
拓展問題2：
有一個整數數列，其中有負數、正數， 其中連續的幾個數求和，求和的絕對值最大的數字串。
分析
思路

最大子矩陣和

#include <iostream> #include <cstdio> using namespace std; #include <memory.h>int a[102][102];int maxSubArray(int *arr, int len) //最大子序列和 {int i,sum=arr[0],b=0;for(i=0;i<len;++i){if(b>0)b+=arr[i];elseb=arr[i];if(b>sum)sum=b;}return sum; } int maxSubMatrix(int n, int m,int array[102][102]) {int i,j,h,max,sum=-100000;int b[102];for(i=0;i<n;i++){memset(b,0,sizeof(b)); //初始化b[]for(j=i;j<n;j++) //把第i行到第j行相加,對每一次相加求出最大值{for(h=0;h<m;h++){b[h]+=array[j][h]; //二維數組壓縮成一維數組，然后求最大子序列和}max=maxSubArray(b,h); if(max>sum)sum=max;}}return sum; } int main(void) {int n,i,j;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++){for(j=0;j<n;j++)scanf("%d",&a[i][j]);}printf("%d\n",maxSubMatrix(n,n,a));}return 0; }

總結

以上是生活随笔為你收集整理的程序员面试100题之九：求子数组的最大和的全部內容，希望文章能夠幫你解決所遇到的問題。

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