因為最近要開始筆試和面試了，我覺得，很有必要做好準備~

這個問題是我在網上看到的，13年一家公司的筆試題，求子數(shù)組的最大和。這個題我之前在微軟的編程之美看到過，不過當時記得并不是很深刻。

現(xiàn)在既然看到了，我就好好的想了想。考試題如下：

上面只給了兩行代碼的空間，也就是說，只需要兩行的代碼即可。

對于這個問題，有種很簡單，但是效率最低的方法，就是枚舉出全部的子數(shù)組，并且求和，比較出最大值。我當初寫的代碼就是這個版本的，現(xiàn)在應該在實驗室的電腦里。

但是，在《編程之美》中，對于這個問題提供了三種解法，而且其中的第三種是效率最高的。時間復雜度O(n)，空間復雜度為O(1)。

其實可以考慮一種比較極端的情況，就是，只有兩個數(shù)，A[0] and A[1]。

這樣，最大值存在的情況，無非就是：A[0], A[0] + A[1], A[1]。

這個過程基本就是三個數(shù)字中，找到最大值的過程。

然后推廣到n的時候，從0->n - 1遍歷只要重復這個過程，就能簡單的獲取到最終的最大值。

那么如何推廣？

假設現(xiàn)在有三個數(shù)字A[3]:A[0] A[1] A[2].

這樣先比較前兩個元素，A[0],A[1],以及A[0] + A[1]。因為下次的比較需要將前面的A[0]+A[1]作為一個整體加入到下一次的比較中，所以需要有一個值能夠用來表示其和。這個變量就是上面的nStart。

nAll則是相當于每次比較中的A[0]。那么每次的比較的順序就是：A[1]和A[0] + A[1]比較。nStart取其最大值，然后在和相當于A[0]的nAll比較。如此往復，當線性遍歷結束的時候，就成功的獲取到了最大值。

這個方法相當巧妙，其中很多的細節(jié)都要自己慢慢的體會。

程序演示截圖：

?

程序代碼：

1 #include <iostream> 2 3 using namespace std; 4 #define max(a, b) (a) > (b) ? (a) : (b) 5 int MaxSubArray(int * A, int n) 6 { 7 int nStart = A[0]; 8 int nAll = A[0]; 9 for(int i = 1;i < n;++ i) 10 { 11 nStart = max(A[i], nStart + A[i]); 12 nAll = max(nStart, nAll); 13 } 14 return nAll; 15 } 16 int main() 17 { 18 cout << "Hello world!" << endl; 19 int array[] = {10, -1, 3, -11, -20, 33, 1, -6, 13}; 20 cout << MaxSubArray(array, sizeof(array)/sizeof(int)) << endl; 21 return 0; 22 }

?

轉載于:https://www.cnblogs.com/matrix-r/p/3319053.html

總結

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

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