問題

前兩天看到一道算法題, 想了幾天, 然后到網上搜了搜, 基本和我想到的相契合. 來, 題目如下:

給出一個數組, 求出和最大的連續子集. 舉個例子: 數組?[1, 2, 3, 4, 5]?那和最大的就是數組本身了.

但是, 如果中間出現負數, 那情況立刻就不一樣了, 你需要考慮是否能夠將負數左邊的內容包含進來, 從而令子集的和最大化.

下面給出本人遞進的思考思路.

方案一

暴力一點, 直接遍歷所有情況. 暴力破解沒什么好說的, 下面是 php 代碼:

$arr = []; // 一個數組 $maxSum = 0; for($i = 0; $i < count($arr); $i++){for ($j = $i; $j < count($arr); $j++){// 計算當前子集的和$sum = 0;for ($n = $i; $n <= $j; $n++) $sum += $arr[$n];if($sum > $maxSum) $maxSum = $sum;} }

上面代碼很好理解, 將所有子集都遍歷一遍, 然后比較是否是最大的和. 簡單粗暴, 就是時間復雜度有些高: O(n^3)

方案二

仔細觀察上面的方案, 你會發現其實是可以減少一次循環的. 第三層循環不過是將第二層的內容進行逐次累加, 也就是第二層循環的第 n 次累加結果, 正好是第 n+1次的倒數第二條結果. 如果將這樣的結果進行向后傳遞, 就可以將第三層循環減掉了.

$arr = []; // 一個數組 $maxSum = 0; for($i = 0; $i < count($arr); $i++){$sun = 0;for ($j = $i; $j < count($arr); $j++){$sum += $arr[$j];if($sum > $maxSum) $maxSum = $sum;} }

看這段代碼, 和方案一實現的內容其實是一樣的, 但減少了一次循環, 時間復雜度直接降低了一個檔次: O(n^2)

你以為到此為止了么? 天真, 如果這么簡單, 那我還寫個毛啊. 再來.

方案三

時間復雜度再往下降, 好吧, 我承認, 下面這段代碼是我看到網上其他大佬的方案后才恍然大悟的. 恕在下愚鈍. 先看代碼:

$maxSum = 0; // 至今的最大值 $maxHere = 0; // 遍歷到此的最大值 for($i = 0; $i < count($arr); $i++){$maxHere = max($maxHere + $arr[$i], 0);$maxSum = max($maxSum, $maxHere); }

以上代碼時間復雜度為 O(n). 很牛逼. 因為這個方法不是咱想出來的, 咱就不分析他是如何出來的了, 簡單看一看她為什么能夠求出結果值.

當遍歷到$i 的位置時,?maxHere?保存了?i-1?的最大和. 若加上當前值為正數, 則可以繼續往后加, 因為正數相加必然令數字變大. 但如果相加結果為負數, 則將其重置為0 , 因為負數相加必然令數字變小. 所以 第三行 取相加結果與0的較大值.

每次遍歷之后,?maxHere?變量都保存了前面至當前位置的最大和, 將其與maxSum?比較即可. 至此, 即可完成時間復雜度 O(n) .

總結

其實, 當最終結果擺到我面前的時候, 我會有一種恍然大悟的感覺. 但我之前在方案二卡了幾天, 沒有想到 O(n) 的算法. 是思維限制了我? 是智商拉低了我? 還是僅僅因為我沒有與其打過照面??

很多問題都是這樣, 當答案明明白白擺在你面前的時候, 你會覺得, 哼不過如此, 故弄玄虛. 但如果不告訴你答案, 你就是絞盡腦汁, 費盡氣力, 燃燒你的卡路里, 也想不到這個答案. 這感覺就像是大名鼎鼎的 NP 問題, 當答案擺在你面前時, 你能夠輕而易舉的驗證它, 但如果不告訴你答案, 你就是得不到它.

讓我想起了我當初學數學的時候, 很多題目給我的感覺也是這樣. 當看過答案之后, 我會發現, 哦不過如此, so easy. 但是, 當時考試的時候就是沒有寫出來. 當時是如何解決這種情況呢? 大量做題. 俗話說, 熟能生巧, 熟讀唐詩三百首, 不會作詩也會吟. 說的都是重復的力量. 我雖然英語是個渣渣, 但是?public?cost?class?這些詞, 我一看就會, 為什么? 每天都在寫, 想不會都難啊.

說下來, 如何解決上面的問題呢? 簡單說, 多做題. 或者說, 當你解決類似的問題多了, 再次遇到它, 不用說, 下意識就會將解決方案從記憶中檢索出來, 并將方案改造成適合當前場景的樣子.

重在參與嘛. 將前幾天困擾自己幾天的問題記錄一下, 雖然現在看很 low. 當然, 但愿下次看到能夠想起解決方案.

總結

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

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