連續子數組最大和

連續子數組最大和

輸入一個整型數組（正、負數均有），數組中一個或連續的多個整數組成一個子數組，求所有子數組的最大值。

要求時間複雜度為O(n)

例：輸入數組為, 和最大的子數組為, 因此輸出為該子數組的和為18

思路分析

最直接的解法：枚舉所有子數組並求它們的和。長為n的數組，共有n*(n + 1)/2個子數組。計算出所有子數組之和，最快需要O(n^2)，顯然不符合要求

思路一 舉例分析數組規律

通常，舉例能夠具象化演算法，讓你能夠更直觀的看到問題，解演算法題時，碰到不好解決的問題，可以嘗試舉例分析問題規律，降低問題難度

從頭到尾逐個累加例中每個數字。初始化和為0：

加1 和為1

加-2 和為-1

加3 上一步的累積和為負數，那麼我們不用考慮之前的累積和，從第一個數字開始的子數組也不用考慮 —— 從第三個數開始重新累加 和為3

加10 和為13

加-4 和為9 —— 因為-4為負，加上-4後會是累加和變小，所以可以把上一步的13當做暫時發現的最大子和值

加7 和為16，比之前的最大值13大，更新Result為16

加2 和為18，更新Result為18

加-5 和為13

依據上述步驟，可以確定最大子和是18

思路二 應用動態規劃

應用遞歸思想

當以第i-1個數字結尾的子數組中所有數字之和小於0時，如果把這個負數與i個數累加，得到的結果比第i個數本身還要小，所以這種情況下以第i個數字結尾的子數組就是第i個數字本身；

如果以第i-1個數字結尾子數組中所有數字的和大於0，與第i個數字累加就得到以第i個數字結尾的子數組中所有數字的和

用遞歸的方式分析動態規劃問題，最終都是使用循環解決

SourceCode – C++

code in text

薦&往

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！