1. 先把問題嚼透什么是最大子數(shù)組和如果你刷過一段時間的算法題肯定繞不開這道“最大子數(shù)組和”。它幾乎出現(xiàn)在每一份面試題單里也是動態(tài)規(guī)劃入門時繞不開的經(jīng)典案例。題目本身很簡單給定一個整數(shù)數(shù)組找一個具有最大和的連續(xù)子數(shù)組返回這個最大和。注意關(guān)鍵詞是“連續(xù)”這意味著你不能跳著選元素子數(shù)組必須是原數(shù)組中一段緊挨著的區(qū)間。舉個例子數(shù)組是[-2, 1, -3, 4, -1, 2, 1, -5, 4]肉眼掃一下最大的連續(xù)子數(shù)組是[4, -1, 2, 1]和為6。這個結(jié)果很直觀但真正困難的是當數(shù)組長度變成幾萬、幾十萬怎么用程序高效地找出來你總不能把所有連續(xù)子數(shù)組都列出來一個個求和吧這篇文章我想把三種經(jīng)典解法從頭到尾講透暴力枚舉法、分治法和動態(tài)規(guī)劃法。這三種方法代表了三層遞進的思考方式從“無腦遍歷”到“分而治之”再到“用數(shù)學(xué)歸納法的思想做決策”。無論你是剛開始學(xué)算法的新手還是準備面試的求職者或者純粹想復(fù)習基礎(chǔ)知識的開發(fā)者都能從里面拿到一些可以立刻上手的東西。尤其是最后一種動態(tài)規(guī)劃法它是面試中最愛考、效率也最高的解法值得你花時間徹底吃透。我自己的經(jīng)驗是這道題的價值不在“背答案”而在于它能把動態(tài)規(guī)劃最重要的思想——狀態(tài)定義、狀態(tài)轉(zhuǎn)移、空間優(yōu)化——全部串起來。刷完這道題你對動態(tài)規(guī)劃的感覺會完全不同。2. 暴力枚舉法從最原始的思路出發(fā)2.1 三重循環(huán)直接枚舉起點和終點剛接觸這道題的人第一反應(yīng)通常都是暴力枚舉把所有的子數(shù)組都找出來分別求最大值。實現(xiàn)起來也非常簡單使用兩層循環(huán)分別控制子數(shù)組的起點i和終點j再寫一層循環(huán)計算從i到j(luò)的和然后不斷更新最大值。def max_subarray_brute_force(nums): n len(nums) max_sum float(-inf) for i in range(n): for j in range(i, n): current_sum 0 for k in range(i, j 1): current_sum nums[k] max_sum max(max_sum, current_sum) return max_sum這段代碼的邏輯非常直白但問題也很致命三層循環(huán)嵌套時間復(fù)雜度是 O(n^3)。如果你拿一個一萬個元素的數(shù)組去測運行時間會感人到讓你懷疑人生。原因很簡單——我們重復(fù)計算了大量區(qū)間和。比如你算完了nums[i:j]的和下個循環(huán)要算nums[i:j1]時又從頭把nums[i]加到nums[j1]前面算過的結(jié)果完全沒有利用上。這就是暴力法最大的問題不是錯是傻。但在實際面試中先提出暴力法再逐步優(yōu)化是一個非常標準的解題節(jié)奏。它至少幫你確認了一件事題目沒有理解錯枚舉所有區(qū)間肯定是能得到正確答案的。這就相當于你到了一個陌生的城市先畫一張粗糙的地圖再慢慢細化精確路線。2.2 用前綴和消除最內(nèi)層循環(huán)既然每次都重新求和太浪費那就想辦法把“求和”變成“查表”。前綴和數(shù)組的經(jīng)典做法是先預(yù)處理一個數(shù)組prefix其中prefix[i]表示nums[0]到nums[i-1]的和通常prefix[0] 0方便計算。這樣求區(qū)間nums[i:j]的和只需要一步減法prefix[j1] - prefix[i]。def max_subarray_prefix(nums): n len(nums) prefix [0] * (n 1) for i in range(n): prefix[i 1] prefix[i] nums[i] max_sum float(-inf) for i in range(n): for j in range(i, n): current_sum prefix[j 1] - prefix[i] max_sum max(max_sum, current_sum) return max_sum這樣時間復(fù)雜度從 O(n^3) 降到了 O(n^2)空間復(fù)雜度變成 O(n)用來存前綴和數(shù)組。別小看這一步優(yōu)化它其實是“空間換時間”思想的典型體現(xiàn)。你犧牲了一點內(nèi)存換掉了重復(fù)計算這在工程上很常見。還有一個細節(jié)值得注意前綴和數(shù)組多開一位讓prefix[0] 0是為了讓區(qū)間從0開始時也能用同一個公式表達。這個習慣我在處理大量區(qū)間求和問題時都會保持省得寫一堆if i 0的特判。當然O(n^2) 的復(fù)雜度在面試里還是不夠看的。如果數(shù)組長度是十萬O(n^2) 意味著上百億次操作現(xiàn)實場景完全頂不住。但從暴力到前綴和的這個過程你已經(jīng)展現(xiàn)出了“發(fā)現(xiàn)問題并優(yōu)化”的能力這在面試中是有加分的。前面兩步只是熱身接下來的兩種方法才是真正的核心。2.3 暴力法的真正價值你可能會問既然后面有更優(yōu)解法為什么還要花時間搞懂暴力法我個人的體會是暴力法是驗證你對題目理解是否正確的試金石。尤其是當你實現(xiàn)完優(yōu)化的算法后拿一個隨機生成的小規(guī)模數(shù)組用暴力法的結(jié)果和優(yōu)化算法的結(jié)果互相對拍這是最常見的自查手段。我平時寫代碼哪怕是處理一些業(yè)務(wù)邏輯也喜歡先用最容易讀懂的方式寫一個版本作為后續(xù)性能優(yōu)化的參照物。這不是浪費時間而是幫你建立起“優(yōu)化后結(jié)果依然正確”的信心。暴力法雖然效率低但它的正確性幾乎不可能出問題這就是它最大的價值。3. 分治法把大問題切成兩半想3.1 核心思想最大子數(shù)組只會出現(xiàn)在三個地方分治法的思路是和“連續(xù)”這個性質(zhì)強相關(guān)的。我們把數(shù)組從中間分成左右兩半那么要找的最大子數(shù)組只會出現(xiàn)在三個位置完全落在左半部分完全落在右半部分跨越了中間的分界線。前兩種情況很好辦遞歸去左半邊和右半邊分別求最大子數(shù)組和就行。麻煩的是第三種情況跨中點的最大子數(shù)組。這里的核心觀察是如果一個子數(shù)組跨越了中點mid那么它必須包含nums[mid]和nums[mid1]。更準確地說它可以被拆成兩部分從mid向左延伸的某個后綴加上從mid1向右延伸的某個前綴。于是跨中子數(shù)組的最大和就是“從mid向左的最大后綴和”加“從mid1向右的最大前綴和”。注意這里必須是連續(xù)的向左的部分必須終止于mid向右的部分必須起始于mid1。明白了這一點剩下的就是寫清楚遞歸和合并邏輯。3.2 跨中點最大和的求解過程我們來寫一個輔助函數(shù)cross_max(nums, left, mid, right)專門計算跨越中點的情況。它的做法是從mid開始向左累加記錄過程中能得到的最大值再從mid1開始向右累加也同樣記錄最大值。兩個最大值相加就是跨中點子數(shù)組的最大和。def cross_max(nums, left, mid, right): left_sum float(-inf) current_sum 0 for i in range(mid, left - 1, -1): current_sum nums[i] left_sum max(left_sum, current_sum) right_sum float(-inf) current_sum 0 for j in range(mid 1, right 1): current_sum nums[j] right_sum max(right_sum, current_sum) return left_sum right_sum為什么向左和向右要分開求最大值再相加而不是直接對整段求最大子數(shù)組因為我們要保證結(jié)果“跨過中點”。如果只在整個區(qū)間里用一次普通的最大子數(shù)組算法得到的可能是完全落在左邊或者完全落在右邊的結(jié)果那就不叫“跨中點”了。分開求的過程中向左的部分強制包含mid向右的部分強制包含mid1組合起來才滿足跨越條件。這里有一個細節(jié)容易踩坑循環(huán)的邊界條件。向左遍歷時循環(huán)是從mid遞減到left注意mid本身是包含在內(nèi)的向右遍歷時從mid 1遞增到right。很多朋友在寫的時候會把mid漏掉或者把right寫成n導(dǎo)致結(jié)果出錯。這種錯誤用前面提到的“和暴力法對拍”的方法一測就能暴露出來。3.3 遞歸主框架與復(fù)雜度分析寫好了跨中點函數(shù)剩下的主邏輯就很清晰了。遞歸的終止條件是區(qū)間只剩一個元素此時最大子數(shù)組和就是這個元素本身。否則就拆成兩半分別遞歸求解再結(jié)合跨中點結(jié)果取最大值。def max_subarray_divide(nums, left, right): if left right: return nums[left] mid (left right) // 2 left_max max_subarray_divide(nums, left, mid) right_max max_subarray_divide(nums, mid 1, right) cross_max_sum cross_max(nums, left, mid, right) return max(left_max, right_max, cross_max_sum)時間復(fù)雜度是 O(n log n)。怎么算出來的遞歸每一層需要線性掃描一遍數(shù)組主要是cross_max這一步左右加起來剛好是n個元素遞歸樹的深度是 log n 層所以總復(fù)雜度是 O(n log n)。空間復(fù)雜度是 O(log n)來自遞歸棧的調(diào)用深度。分治法的優(yōu)點在于它的思想很有普適性。很多看起來“沒法下手”的問題只要你能找到“跨過中間合并”的方式就能用分治解決。它也是歸并排序、快速排序這些經(jīng)典排序算法的底層思想。雖然它的復(fù)雜度比不上動態(tài)規(guī)劃但它在整個算法知識體系里的地位非常重要。我推薦新手階段就把分治的套路練熟因為后面遇到樹結(jié)構(gòu)、區(qū)間查詢、歸并求逆序?qū)Φ葐栴}時你會發(fā)現(xiàn)它們的思想是一脈相承的。分治法的代碼實現(xiàn)還有一個常見錯誤在遞歸函數(shù)里每次重新創(chuàng)建數(shù)組切片比如把nums[left:mid1]傳給下一次遞歸。這樣做不僅引入了額外空間開銷還會讓索引變得混亂。更好的做法是始終使用同一個數(shù)組只傳遞區(qū)間下標。這個習慣能讓你減少很多不必要的 debug 時間。4. 動態(tài)規(guī)劃法Kadane算法為什么是神4.1 狀態(tài)定義為什么必須“以 i 結(jié)尾”動態(tài)規(guī)劃法的核心是定義dp[i]表示“以nums[i]結(jié)尾的連續(xù)子數(shù)組的最大和”。第一次看到這個定義的人都會困惑為什么不直接定義成“前 i 個元素的最大子數(shù)組和”如果定義成后者轉(zhuǎn)移的時候會遇到一個尷尬的問題你沒法確定“前 i 個元素的最大子數(shù)組”到底是以第幾個元素結(jié)尾的如果最后一個子數(shù)組的末尾不是nums[i-1]那它和nums[i]根本連不上。這就是“最優(yōu)子結(jié)構(gòu)”在這個題目里的關(guān)鍵陷阱。“以 i 結(jié)尾”的定義之所以精妙就在于它強制子數(shù)組延續(xù)到當前位置。那么當掃描到nums[i]時只有兩種選擇把nums[i]接在“以i-1結(jié)尾的最大子數(shù)組”后面形成一個新的連續(xù)子數(shù)組拋棄前面所有的累加值讓nums[i]自己單獨成為一個新的子數(shù)組。你可能會覺得第一種選擇看起來總是更好畢竟前面累加了那么多。但別忘了如果前面的和是負數(shù)強行加上反而是累贅。比如數(shù)組是[-5, 2]如果非要接上-5結(jié)果變成-3還不如直接從2開始。所以狀態(tài)轉(zhuǎn)移方程就是dp[i] max(dp[i-1] nums[i], nums[i])。為什么這樣定義后最終答案就是max(dp[0], dp[1], ..., dp[n-1])因為最大子數(shù)組的終點必然是數(shù)組中的某一個位置它的和就是對應(yīng)的dp值。相當于我們枚舉了所有可能的“子數(shù)組結(jié)尾位置”取其中的最大值。4.2 空間優(yōu)化從一維數(shù)組到單個變量既然dp[i]只依賴dp[i-1]完全沒有必要把所有中間結(jié)果存下來。用一個變量滾動更新即可這樣空間復(fù)雜度從 O(n) 降到 O(1)。def max_subarray_kadane(nums): current_sum nums[0] max_sum nums[0] for i in range(1, len(nums)): current_sum max(current_sum nums[i], nums[i]) max_sum max(max_sum, current_sum) return max_sum這段代碼簡潔得讓人懷疑這么復(fù)雜的問題就這幾行但越簡潔的代碼越考驗?zāi)銓Ρ举|(zhì)的把握。current_sum代表的其實就是“以當前元素結(jié)尾的最大子數(shù)組和”max_sum記錄歷史上出現(xiàn)過的最大值。每次循環(huán)我們只關(guān)心兩件事接上當前元素是否劃算以及當前結(jié)果是否刷新了歷史最佳。這里還有一個容易犯的初始化錯誤把current_sum和max_sum初始化為0。如果數(shù)組中全是負數(shù)初始化成0就會導(dǎo)致最終答案錯誤。比如數(shù)組是[-3, -5, -1]最大子數(shù)組和應(yīng)該是-1。但如果從0開始current_sum永遠停留在0因為負數(shù)加上去會變小。所以正確的初始化方式是用數(shù)組的第一個元素這也是為什么上面代碼里先賦值nums[0]再開始循環(huán)。這個坑在面試中非常常見十個人里至少有四個人會踩。4.3 Kadane算法背后的動態(tài)規(guī)劃思想Kadane算法本質(zhì)上就是動態(tài)規(guī)劃只不過因為狀態(tài)轉(zhuǎn)移足夠簡單很多人沒有意識到這一點。它的時間復(fù)雜度是 O(n)空間復(fù)雜度是 O(1)理論上已經(jīng)是求解“最大子數(shù)組和”的最優(yōu)解法。因為至少要遍歷一次數(shù)組才能知道所有元素的情況所以 O(n) 就是下限。對于剛學(xué)動態(tài)規(guī)劃的朋友我強烈建議你手動模擬一遍這個過程。拿[-2, 1, -3, 4, -1, 2, 1, -5, 4]來說i0current_sum -2max_sum -2i1max(-21, 1) 1max_sum 1i2max(1-3, -3) -2max_sum 1i3max(-24, 4) 4max_sum 4i4max(4-1, -1) 3max_sum 4i5max(32, 2) 5max_sum 5i6max(51, 1) 6max_sum 6i7max(6-5, -5) 1max_sum 6i8max(14, 4) 5max_sum 6最終答案是 6和題目給出的結(jié)果一致。這個過程走一遍你就能真正理解為什么要“貪心地拋棄負數(shù)前綴”因為扔掉負累贅永遠是明智的選擇。注意這里的“貪心”和普通的貪心算法不是一個概念它的依據(jù)是動態(tài)規(guī)劃的遞推關(guān)系并不是每一步只看局部最優(yōu)。不過從效果上看它確實有一種“一旦發(fā)現(xiàn)累加值為負立刻從零開始”的直覺美感。5. 三足鼎立算法對比與實戰(zhàn)選型5.1 復(fù)雜度與適用規(guī)模速查表三種算法放在一起對照各自的定位非常清晰。算法時間復(fù)雜度空間復(fù)雜度核心思想適用場景暴力枚舉法O(n^3)O(1)枚舉所有子數(shù)組小規(guī)模數(shù)據(jù)、驗證正確性前綴和優(yōu)化O(n^2)O(n)空間換時間中等規(guī)模、學(xué)習漸進優(yōu)化分治法O(n log n)O(log n)分而治之、跨中點合并理解遞歸、樹狀分治思想動態(tài)規(guī)劃法O(n)O(1)狀態(tài)轉(zhuǎn)移、滾動更新絕大多數(shù)工程與面試場景從表格中能明顯看出動態(tài)規(guī)劃法在各方面都是壓倒性優(yōu)勢。這也是為什么面試時寫代碼直接用Kadane算法才是正確的答案。但分治法和暴力法也絕不是無用武之地在需要把問題擴展到二維矩陣、或者需要返回具體子數(shù)組區(qū)間時分治法和暴力法的思路有時會給你不一樣的啟發(fā)。5.2 面試和工程里怎么選如果是在面試現(xiàn)場我會建議你先口述暴力法的思路再快速過渡到動態(tài)規(guī)劃。這個過程展示的是你的思維鏈——從最容易想到的方案出發(fā)識別其中的重復(fù)計算進而設(shè)計更優(yōu)的狀態(tài)定義。這種展示方式比直接甩出最優(yōu)解法更有說服力因為面試官想看到的是你如何思考而不是你記憶力有多好。在真正的工程代碼里最大子數(shù)組和問題很少會以裸題形式出現(xiàn)更多是作為某個復(fù)雜系統(tǒng)里一個內(nèi)部步驟。比如處理傳感器時序數(shù)據(jù)時找出信號最強烈的連續(xù)時間段或者在日志分析中找到某類錯誤持續(xù)爆發(fā)的連續(xù)區(qū)間。這些場景的數(shù)據(jù)量動輒幾十萬O(n^2) 根本跑不動所以直接上動態(tài)規(guī)劃法是最穩(wěn)妥的。但如果你還額外需要知道“最大和對應(yīng)的子數(shù)組具體是從哪個下標到哪個下標”就得多寫幾行代碼在更新max_sum時同步記錄起點和終點。這里我再補一個工程細節(jié)當數(shù)組長度為0時Kadane算法會直接訪問nums[0]從而拋出異常。所以真正落地時需要做空數(shù)組的判斷并約定一個特殊返回值比如返回0還是拋出異常取決于業(yè)務(wù)語義。很多人刷題時不會遇到空數(shù)組的測試用例但在真實的業(yè)務(wù)代碼里空數(shù)組的情況太常見了這一行防御性判斷應(yīng)該成為習慣。6. 延伸思考變體問題與實戰(zhàn)經(jīng)驗6.1 四個值得研究的變體問題最大子數(shù)組和之所以經(jīng)典是因為它有一大堆變體每一個都能考察你對基礎(chǔ)版的理解深度。第一個變體是“返回最大子數(shù)組的起止下標”。解法是在Kadane算法進行中當current_sum被重置為nums[i]時記錄新的起點為i當max_sum被刷新時記錄當前的終點為i。這樣最終就能找到對應(yīng)的區(qū)間。第二個變體是“環(huán)形數(shù)組的最大子數(shù)組和”。環(huán)形數(shù)組意味著子數(shù)組可以繞過最后一個元素回到開頭。比如[5, -3, 5]普通線性掃描得到最大子數(shù)組和是7[5, -3, 5]但環(huán)形情況下其實整個數(shù)組都是正收益最大和是7但如果數(shù)組是[5, -3, 5, 5, -3]情況就變得更復(fù)雜。經(jīng)典做法是分兩種情況討論最大子數(shù)組不跨越邊界直接用普通Kadane最大子數(shù)組跨越邊界等價于“數(shù)組總和減去最小子數(shù)組和”。取兩種情況的最大值即可。不過有個特殊情況如果數(shù)組全是負數(shù)總和減去最小子數(shù)組和會得到一個負數(shù)此時取普通Kadane的結(jié)果更合理需要額外判斷。第三個變體是“二維矩陣的最大子矩陣和”。做法是把矩陣的若干行壓縮成一個一維數(shù)組再對這個數(shù)組套用Kadane算法。具體來說枚舉矩形的上下邊界把每一列對應(yīng)區(qū)間的元素累加成一個一維數(shù)組然后用一維最大子數(shù)組和找橫向最大值。枚舉上下邊界是 O(n^2)每輪跑一次Kadane是 O(m)總復(fù)雜度是 O(n^2 * m)。這個方法在實際面試中遇到的可能性不大但能掌握的話會讓你對動態(tài)規(guī)劃的理解更上一層。第四個變體是“最大子序列和”也就是允許任意跳選的子序列而不是連續(xù)子數(shù)組。這個問題反而簡單把所有正數(shù)累加就是答案如果全是負數(shù)就取最大的負數(shù)。雖然解法簡單但它提醒我們一個重要的區(qū)分連續(xù)和離散的約束直接改變了問題的難度層級。6.2 刷這道題時我總結(jié)的幾個自查方法我做算法題有個習慣就是寫完代碼后先不急著提交而是用幾個特別設(shè)計的例子做自查。對最大子數(shù)組和來說我一定會測以下幾類數(shù)據(jù)第一個是全負數(shù)數(shù)組比如[-3, -2, -1]。這個用例專門檢測初始化值有沒有寫錯如果返回了0說明初始化邏輯有 bug。第二個是只有一個元素的數(shù)組比如[7]。這個用例檢測邊界條件很多遞歸實現(xiàn)會在區(qū)間長度為1時出錯。第三個是正負交替的數(shù)組比如[1, -2, 3, -1, 2]用來確認算法能正確處理“拋棄負數(shù)前綴再重新累加”的場景。第四個就是全正數(shù)數(shù)組比如[1, 2, 3, 4]此時答案應(yīng)該是所有元素之和用來檢測是否漏掉了某個位置的更新。還有一個調(diào)試技巧當代碼結(jié)果不對時在Kadane算法的循環(huán)里打印i、current_sum、max_sum三個變量跟著輸出走一遍往往幾秒鐘就能定位到問題。比盯著一堆代碼空想要高效得多。分治法的遞歸實現(xiàn)如果出錯建議在遞歸函數(shù)入口打印當前的left和right看看遞歸拆分是否符合預(yù)期同時把cross_max的結(jié)果單獨驗證因為這一塊是最容易寫錯邊界的地方。我在實際工作中還發(fā)現(xiàn)一個有意思的場景做數(shù)據(jù)監(jiān)控時假設(shè)某個指標每天有一個波動值想找出一段“連續(xù)增長最猛”的時間窗口本質(zhì)上就是在求最大子數(shù)組和。把每天的波動值放進數(shù)組跑一遍Kadane算法就能知道哪段時間整體表現(xiàn)最強。這種從算法題到工程應(yīng)用的遷移感是刷題最讓人上癮的地方。最后再說說這道題留給我的一個深刻印象動態(tài)規(guī)劃的狀態(tài)定義一定要貼合“轉(zhuǎn)移的需要”。有時候你定義的dp[i]看起來差不太多但“差之毫厘謬以千里”。在做其他動態(tài)規(guī)劃題目時比如最長遞增子序列、背包問題我都會先停下來認真想清楚——當前狀態(tài)到底應(yīng)該“以 i 結(jié)尾”還是“前 i 個元素”這個選擇直接決定整個算法的成敗。最大子數(shù)組和這道題教會我的正是這種狀態(tài)定義的敏感性。