橋杯最大子陣：動態(tài)規(guī)劃二維降一維的C++實現(xiàn)與優(yōu)化詳解)
先聊一聊這道題的江湖地位。藍(lán)橋杯歷屆試題里最大子陣算是非常有代表性的一道動態(tài)規(guī)劃題。說它代表性不是因為算法本身有多冷門而是它完美演示了一個核心思想把二維問題降維成一維問題再用經(jīng)典算法去解決。我在刷題群里見過不少同學(xué)看到“矩陣”“子陣”這種字眼就先慌了以為要上什么高級數(shù)據(jù)結(jié)構(gòu)其實這道題只要想通“壓縮”這兩個字代碼量很小思路也清晰。這篇文章會把從暴力到優(yōu)化的完整推導(dǎo)、C實現(xiàn)細(xì)節(jié)、還有我踩過的幾個坑都寫清楚適合剛?cè)腴T動態(tài)規(guī)劃、準(zhǔn)備藍(lán)橋杯C組比賽的同學(xué)也適合希望把最大子段和擴展成二維場景的讀者。1. 題目拆解與核心思路1.1 從一維最大子段和說起先回到最基礎(chǔ)的問題給你一個一維數(shù)組要求找出和最大的連續(xù)子段。這本是動態(tài)規(guī)劃里的經(jīng)典題也是Kadane算法的用武之地。Kadane算法的核心邏輯可以用一句話概括記錄以當(dāng)前位置結(jié)尾的最大子段和同時維護(hù)一個全局最大值。以dp[i]表示以第i個元素結(jié)尾的最大子段和則轉(zhuǎn)移方程為dp[i] max(arr[i], dp[i-1] arr[i])翻譯成人話就是要么從當(dāng)前位置重新開始要么接著前面的子段繼續(xù)加。最終答案是所有dp[i]中的最大值。這個算法之所以經(jīng)典是因為它把暴力枚舉的O(n^2)壓縮到了O(n)。一維的問題搞明白之后二維的最大子陣就有了突破口。1.2 二維最大子陣如何降維最大子陣的題目描述很簡單給定一個n行m列的矩陣找出一塊連續(xù)的子矩陣使得其中所有元素的和最大。最直觀的暴力做法是枚舉四個邊界也就是上邊界、下邊界、左邊界、右邊界。這一步直觀但致命——四重循環(huán)是O(n^4)再加上求和操作總體復(fù)雜度離譜在藍(lán)橋杯的數(shù)據(jù)范圍下絕對跑不動。降維的核心思路是固定上下邊界把每一列的元素累加變成一個一維數(shù)組。這個一維數(shù)組的第k個元素就是原矩陣第k列從第i行到第j行的元素之和。接著對壓縮后的一維數(shù)組跑Kadane算法就得到了當(dāng)前上下邊界范圍內(nèi)和最大的子矩陣。換句話說我們不再同時枚舉左右邊界而是讓一維最大子段和算法幫我們找出最優(yōu)的“左右區(qū)間”。這樣總的枚舉量就從四維降到二維復(fù)雜度從O(n^4)降到了O(n^2 * m)。1.3 為什么暴力在競賽環(huán)境下不可行舉個具體的數(shù)據(jù)感受一下數(shù)量級。假設(shè)n和m都在500左右這是藍(lán)橋杯較常見的規(guī)模。暴力枚舉四個邊界邊界組合數(shù)為O(n^2 * m^2)也就是500^4等于6.25 * 10^10。就算每次求和只用一條語句這個數(shù)量級在單線程下也遠(yuǎn)遠(yuǎn)超過時限。即便對暴力法做一些剪枝優(yōu)化比如用前綴和把求和降到O(1)四重枚舉仍然有O(n^2 * m^2)的組合數(shù)量仍然無法在1秒內(nèi)完成。而采用“固定上下邊界一維DP”的優(yōu)化做法后上下邊界組合數(shù)為O(n^2)每次跑一維DP的代價是O(m)總復(fù)雜度為O(n^2 * m)。500^2 * 500等于1.25 * 10^8在C的優(yōu)化下已經(jīng)可以在1到2秒內(nèi)穩(wěn)定跑完。這也是這道題設(shè)計上的精妙之處它考察的正是降維思維的工程價值。2. 算法設(shè)計細(xì)節(jié)2.1 前綴和預(yù)處理行方向還是列方向要想在固定上下邊界后快速獲得每一列的和需要提前構(gòu)建前綴和數(shù)組。通常有兩種選擇。第一種是sum[i][j]表示第j列前i行的元素和這樣第k列在上下邊界top和bottom之間的和可以直接用sum[bottom][k] - sum[top-1][k]計算。第二種是構(gòu)建行的前綴和再按列壓縮。我在實際做題時更習(xí)慣用第一種列方向的前綴和因為固定上下邊界后我需要頻繁按列取區(qū)間和。用colSum[i][j]表示第j列前i行的累計和代碼上就是for (int j 1; j m; j) { for (int i 1; i n; i) { colSum[i][j] colSum[i-1][j] matrix[i][j]; } }這樣后續(xù)壓縮數(shù)組時只需一行代碼temp[k] colSum[bottom][k] - colSum[top-1][k];前綴和的意義不只是減少計算量它還能讓代碼邏輯更清晰。colSum數(shù)組直接表達(dá)了“從第top行到第bottom行第k列的總和”不需要再寫內(nèi)層循環(huán)臨時累加避免了不少低效操作。2.2 枚舉上邊界與下邊界枚舉上下邊界是二維降維的第一步。需要注意的是上下邊界的組合一共有n * (n1) / 2種因為上邊界可以是從第1行到第n行的任意一行下邊界必須大于等于上邊界。有的同學(xué)會習(xí)慣寫成for (int top 1; top n; top) { for (int bottom top; bottom n; bottom) { // 處理當(dāng)前上下邊界 } }這里有個容易忽略的細(xì)節(jié)當(dāng)top等于bottom時意味著子陣只有一行此時它退化成一維最大子段和問題。這種情形也必須覆蓋否則會漏解。而枚舉過程中這個情形天然被包含在內(nèi)不需要單獨寫特殊判斷。這是枚舉寫法的一個好處不需要為“單行子陣”單獨編碼。我自己的習(xí)慣是在內(nèi)層循環(huán)里先初始化temp數(shù)組把當(dāng)前上下邊界下每一列的和算好然后再去跑一維DP。每更換一組上下邊界temp數(shù)組都會被重新計算這是整個算法最核心的循環(huán)體。2.3 動態(tài)規(guī)劃求解壓縮后的一維數(shù)組拿到temp數(shù)組之后就要用一維最大子段和的思路找出當(dāng)前上下邊界下的最優(yōu)左右區(qū)間。這里的DP實現(xiàn)可以不用額外開數(shù)組用滾動變量就行int cur 0; int best INT_MIN; for (int k 1; k m; k) { cur max(temp[k], cur temp[k]); best max(best, cur); }這段代碼看起來很簡潔但里面藏著一個關(guān)鍵細(xì)節(jié)cur的初值。我見過很多初次接觸這道題的同學(xué)把cur初始化為0這在一維最大子段和的某些寫法中可以工作但在二維場景下會引入一個隱蔽的bug——當(dāng)整個temp數(shù)組全是負(fù)數(shù)時cur永遠(yuǎn)加不出正確的最大值因為cur從0開始max(temp[k], cur temp[k])會把每個負(fù)數(shù)都被0“拉”回來最終可能算出一個不存在的“空子陣”答案0。正確的做法是把cur初始化為0但配合best取INT_MIN或者在一開始的cur max(temp[k], cur temp[k])中保證第一項參與比較。我用的是把best設(shè)為INT_MIN這樣即使矩陣全為負(fù)數(shù)最終答案也是一塊真實存在的最小子陣而不是虛構(gòu)的0。2.4 復(fù)雜度分析這套算法的時間復(fù)雜度可以這樣拆解構(gòu)建列前綴和數(shù)組O(n * m)。枚舉上下邊界O(n^2)組。每組邊界內(nèi)計算temp數(shù)組O(m)。每組邊界內(nèi)跑一維DPO(m)?？傮w復(fù)雜度為O(n^2 * m n * m)主導(dǎo)項是O(n^2 * m)。空間復(fù)雜度為O(n * m)用于存儲矩陣和前綴和數(shù)組。以n500、m500為例最內(nèi)層的計算量約為1.25 * 10^8次操作C在開啟O2優(yōu)化后完全能跑進(jìn)1到2秒。對比暴力四重枚舉的10^10級別這個優(yōu)化帶來的提升是數(shù)量級的也是競賽中最看重的部分。3. C代碼實現(xiàn)與關(guān)鍵注釋3.1 完整可運行代碼下面給出可直接提交的完整代碼我用的是C11標(biāo)準(zhǔn)適配藍(lán)橋杯的常見編譯環(huán)境。#include iostream #include algorithm #include climits using namespace std; const int MAXN 505; int matrix[MAXN][MAXN]; int colSum[MAXN][MAXN]; int temp[MAXN]; int main() { int n, m; cin n m; for (int i 1; i n; i) { for (int j 1; j m; j) { cin matrix[i][j]; } } // 構(gòu)建列方向前綴和colSum[i][j]表示第j列前i行的和 for (int j 1; j m; j) { for (int i 1; i n; i) { colSum[i][j] colSum[i-1][j] matrix[i][j]; } } int ans INT_MIN; // 枚舉上邊界 for (int top 1; top n; top) { // 枚舉下邊界 for (int bottom top; bottom n; bottom) { // 當(dāng)前上下邊界下將每列的和壓縮到temp數(shù)組中 for (int k 1; k m; k) { temp[k] colSum[bottom][k] - colSum[top-1][k]; } // 對temp數(shù)組跑一維最大子段和 int cur 0; for (int k 1; k m; k) { cur max(temp[k], cur temp[k]); ans max(ans, cur); } } } cout ans endl; return 0; }這段代碼沒有冗余的函數(shù)封裝所有邏輯都在main函數(shù)中順序展開。對于競賽環(huán)境來說這反而是更穩(wěn)妥的寫法可以避免函數(shù)調(diào)用的潛在開銷也讓調(diào)試時更容易定位變量問題。3.2 關(guān)鍵變量設(shè)計思路三個數(shù)組各司其職matrix[MAXN][MAXN]存儲原始矩陣。下標(biāo)從1開始而不是0是為了讓前綴和的定義更自然colSum[i-1][j]在下標(biāo)為0時自動取到0不需要額外初始化邊界。colSum[MAXN][MAXN]存儲列方向前綴和。colSum[i][j]表示第j列前i行所有元素的和。這樣設(shè)計是因為在枚舉上下邊界時我需要的是“第k列從top到bottom的和”用兩個前綴和相減即可得到。temp[MAXN]是每次枚舉上下邊界時生成的臨時數(shù)組長度等于列數(shù)m用于承載降維后的一維數(shù)組。使用全局?jǐn)?shù)組能自動初始化為0也避免了在棧上開大數(shù)組導(dǎo)致棧溢出。MAXN取505是因為藍(lán)橋杯的常見數(shù)據(jù)范圍在500左右多留一點余量防止越界。3.3 邊界條件和數(shù)據(jù)類型的經(jīng)驗之談這道題有兩個邊界細(xì)節(jié)需要特別注意第一是負(fù)數(shù)處理。題目并沒有保證矩陣元素全為正數(shù)所以初始答案ans不能設(shè)為0。如果矩陣中所有元素都是負(fù)數(shù)正確答案應(yīng)該是這些負(fù)數(shù)中最大的那個而如果把ans初值設(shè)為0程序會錯誤地輸出0相當(dāng)于虛構(gòu)了一個不存在的空子陣。解決方案有兩種一是用INT_MIN初始化ans二是用-INF大負(fù)數(shù)代替。我習(xí)慣用INT_MIN因為它語義清楚也方便與max配合使用。第二是求和結(jié)果可能超過int范圍。當(dāng)n和m達(dá)到500元素絕對值達(dá)到1000時整個矩陣的和可能達(dá)到2.5 * 10^8雖然int能裝下但為了避免極端數(shù)據(jù)下的溢出風(fēng)險穩(wěn)妥的做法是把累加變量設(shè)為long long。我在訓(xùn)練時吃過這個虧所以現(xiàn)在只要題目沒限制元素大小就默認(rèn)用long long處理累加。如果改用long long只需把數(shù)組類型和ans、cur的類型統(tǒng)一修改即可邏輯不變。3.4 測試樣例驗證用幾個典型樣例來驗證代碼正確性。樣例1常規(guī)正負(fù)混合3 3 1 -1 2 -1 2 -1 2 -1 1模擬可得最大子陣正好覆蓋了所有正數(shù)答案為5。樣例2矩陣全為負(fù)數(shù)2 2 -1 -2 -3 -4最大子陣是單個元素-1答案應(yīng)當(dāng)為-1。此時ans初始化INT_MIN的作用就體現(xiàn)出來cur在第一個元素時取max(-1, 0 (-1))等于-1ans更新為-1。如果初值設(shè)0這里就會輸出0。樣例3單行矩陣1 5 2 -1 3 -2 4這等價于一維最大子段和問題最大子段為2-13-24答案為6。這些樣例跑通后代碼基本就沒有邏輯問題。剩余的風(fēng)險主要來自性能邊界和極端數(shù)據(jù)規(guī)模這兩個方面在下一節(jié)細(xì)講。4. 常見問題與調(diào)試心得4.1 全負(fù)數(shù)矩陣的隱藏陷阱這個問題我在前文提到過但值得單獨拿出來再強調(diào)一次因為它實在太容易踩了。很多教程里寫一維最大子段和時會給出一個初值dp[0] 0的寫法。這個寫法在一維版本下配合“答案初始化為第一個元素”可以工作但如果直接搬到二維代碼里把ans初始化為0就會出現(xiàn)一個嚴(yán)重的邏輯漏洞。我調(diào)試過一位同學(xué)的代碼他的思路是用ans max(ans, cur)逐輪更新但ans初值設(shè)成了0。測試正負(fù)數(shù)混合的樣例全都能過偏偏遇到“全為負(fù)數(shù)”的邊界樣例時輸出永遠(yuǎn)是0而不是真實的最大負(fù)數(shù)。這類問題在比賽中極難發(fā)現(xiàn)因為常規(guī)隨機測試數(shù)據(jù)幾乎必然包含正數(shù)不會觸發(fā)這個bug。建議在寫完這道題后手動測一組全負(fù)數(shù)數(shù)據(jù)這是最直接的驗證方式。4.2 初始化與INF選擇的經(jīng)驗關(guān)于INT_MIN和自定義大負(fù)數(shù)的選擇我來說說自己的偏好。INT_MIN是climits頭文件中定義的常量含義是int類型的最小值直接用它可以少寫一個#define或const int INF -0x3f3f3f3f。自定義大負(fù)數(shù)-0x3f3f3f3f在競賽圈中也很流行原因是它不會溢出且和INT_MIN相比在做加法時不會出現(xiàn)極端下溢。但在本題中cur temp[k]用的cur是從0開始的不會直接用INT_MIN參與加法所以用INT_MIN初始化ans是安全的。如果用了long long版本建議用LLONG_MIN初始化或者用-4e18這類自定義大負(fù)數(shù)。我個人習(xí)慣是直接寫LLONG_MIN因為C標(biāo)準(zhǔn)庫已經(jīng)提供了定義不需要自己拼數(shù)字。4.3 數(shù)組越界與循環(huán)邊界細(xì)節(jié)由于題目給定的下標(biāo)范圍是1到n和1到m數(shù)組要開到至少MAXN n 5的余量。有些同學(xué)習(xí)慣把數(shù)組開得剛剛好比如矩陣是[n][m]在競賽中可能遇到數(shù)組訪問越界到非法內(nèi)存導(dǎo)致莫名其妙的結(jié)果錯誤。我見過一種典型越界場景在構(gòu)建colSum時內(nèi)層循環(huán)從1到n外層循環(huán)從1到m這是正確的但如果把兩個循環(huán)的順序反了并且前綴和更新時寫成了colSum[i][j] colSum[i-1][j] matrix[i][j]那么由于colSum[i-1][j]在使用時依賴于前一行的數(shù)據(jù)必須確保第i-1行已經(jīng)計算完畢。用列優(yōu)先遍歷可以保證這一點但如果用行優(yōu)先就要注意前綴和更新公式的寫法否則會取到未初始化的垃圾值。另一個容易出錯的點是上下邊界枚舉中的top-1。當(dāng)top1時top-10此時colSum[0][k]應(yīng)該是0。因為全局?jǐn)?shù)組默認(rèn)初始化為0所以這個訪問是安全的。但如果你把數(shù)組開成局部變量并忘記初始化這里就會出現(xiàn)隨機值。這也是我建議用全局?jǐn)?shù)組的原因之一。4.4 進(jìn)階變形環(huán)形矩陣與更大數(shù)據(jù)范圍理解最大子陣的降維思路后可以順手拓展幾個相似問題這有助于加深對算法的理解。常見的變形是環(huán)形最大子陣即矩陣的行和列可以循環(huán)跨越邊界。通常的解法是把矩陣復(fù)制一倍變成2n乘2m的新矩陣然后在新矩陣上限制子陣大小不超過n和m再跑最大子陣算法。這需要額外維護(hù)“子陣寬度和高度的限制”也就需要在DP過程中判定區(qū)間長度不能直接套用基礎(chǔ)版代碼。另一個變形是數(shù)據(jù)范圍擴大后的優(yōu)化比如n1000、m1000時O(n^2 * m)達(dá)到了10^9級別直接跑會超時。這時可以把內(nèi)外層循環(huán)調(diào)整固定列邊界而不是行邊界讓復(fù)雜度變?yōu)镺(m^2 * n)選擇較小的維度作為被平方的維度可以有效降低常數(shù)。這些變形本質(zhì)上都在利用“固定一個維度壓縮另一個維度”的思想把它吃透了遇到任何矩陣類的子區(qū)域問題都能更快找到切入點。5. 我個人在實際做題中的一點體會最大子陣這道題我第一次接觸時也走了一些彎路。當(dāng)時第一反應(yīng)是四重枚舉加二維前綴和覺得能算出來就行結(jié)果一提交就超時。后來靜下心去看一維最大子段和的代碼才意識到固定上下邊界這個操作才是整個題目的關(guān)鍵開關(guān)它讓問題從“找矩形”變成了“找一維區(qū)間”難度一下子降低了一個級別。從那以后我遇到二維區(qū)間最值問題都會先問自己一句能不能先固定一個方向把問題壓成一維。這個思維習(xí)慣幫我解決了不少類似的競賽題比如最大子矩陣的變種、帶權(quán)矩陣的最優(yōu)區(qū)域劃分等。最后再分享一個小技巧刷這類動態(tài)規(guī)劃題時不要只盯著標(biāo)準(zhǔn)解法看建議自己先寫一版暴力解再用小數(shù)據(jù)對比優(yōu)化解的輸出確保兩者完全一致。這樣既能驗證正確性也能讓你對優(yōu)化的價值有更直觀的體會。最大子陣作為藍(lán)橋杯歷屆試題中的經(jīng)典題考察的不僅是動態(tài)規(guī)劃更是那種“把復(fù)雜問題簡化成已知問題”的工程直覺值得反復(fù)琢磨。 藍(lán)橋杯最大子陣：動態(tài)規(guī)劃二維降一維的C++實現(xiàn)與優(yōu)化詳解
先聊一聊這道題的江湖地位。藍(lán)橋杯歷屆試題里最大子陣算是非常有代表性的一道動態(tài)規(guī)劃題。說它代表性不是因為算法本身有多冷門而是它完美演示了一個核心思想把二維問題降維成一維問題再用經(jīng)典算法去解決。我在刷題群里見過不少同學(xué)看到“矩陣”“子陣”這種字眼就先慌了以為要上什么高級數(shù)據(jù)結(jié)構(gòu)其實這道題只要想通“壓縮”這兩個字代碼量很小思路也清晰。這篇文章會把從暴力到優(yōu)化的完整推導(dǎo)、C實現(xiàn)細(xì)節(jié)、還有我踩過的幾個坑都寫清楚適合剛?cè)腴T動態(tài)規(guī)劃、準(zhǔn)備藍(lán)橋杯C組比賽的同學(xué)也適合希望把最大子段和擴展成二維場景的讀者。1. 題目拆解與核心思路1.1 從一維最大子段和說起先回到最基礎(chǔ)的問題給你一個一維數(shù)組要求找出和最大的連續(xù)子段。這本是動態(tài)規(guī)劃里的經(jīng)典題也是Kadane算法的用武之地。Kadane算法的核心邏輯可以用一句話概括記錄以當(dāng)前位置結(jié)尾的最大子段和同時維護(hù)一個全局最大值。以dp[i]表示以第i個元素結(jié)尾的最大子段和則轉(zhuǎn)移方程為dp[i] max(arr[i], dp[i-1] arr[i])翻譯成人話就是要么從當(dāng)前位置重新開始要么接著前面的子段繼續(xù)加。最終答案是所有dp[i]中的最大值。這個算法之所以經(jīng)典是因為它把暴力枚舉的O(n^2)壓縮到了O(n)。一維的問題搞明白之后二維的最大子陣就有了突破口。1.2 二維最大子陣如何降維最大子陣的題目描述很簡單給定一個n行m列的矩陣找出一塊連續(xù)的子矩陣使得其中所有元素的和最大。最直觀的暴力做法是枚舉四個邊界也就是上邊界、下邊界、左邊界、右邊界。這一步直觀但致命——四重循環(huán)是O(n^4)再加上求和操作總體復(fù)雜度離譜在藍(lán)橋杯的數(shù)據(jù)范圍下絕對跑不動。降維的核心思路是固定上下邊界把每一列的元素累加變成一個一維數(shù)組。這個一維數(shù)組的第k個元素就是原矩陣第k列從第i行到第j行的元素之和。接著對壓縮后的一維數(shù)組跑Kadane算法就得到了當(dāng)前上下邊界范圍內(nèi)和最大的子矩陣。換句話說我們不再同時枚舉左右邊界而是讓一維最大子段和算法幫我們找出最優(yōu)的“左右區(qū)間”。這樣總的枚舉量就從四維降到二維復(fù)雜度從O(n^4)降到了O(n^2 * m)。1.3 為什么暴力在競賽環(huán)境下不可行舉個具體的數(shù)據(jù)感受一下數(shù)量級。假設(shè)n和m都在500左右這是藍(lán)橋杯較常見的規(guī)模。暴力枚舉四個邊界邊界組合數(shù)為O(n^2 * m^2)也就是500^4等于6.25 * 10^10。就算每次求和只用一條語句這個數(shù)量級在單線程下也遠(yuǎn)遠(yuǎn)超過時限。即便對暴力法做一些剪枝優(yōu)化比如用前綴和把求和降到O(1)四重枚舉仍然有O(n^2 * m^2)的組合數(shù)量仍然無法在1秒內(nèi)完成。而采用“固定上下邊界一維DP”的優(yōu)化做法后上下邊界組合數(shù)為O(n^2)每次跑一維DP的代價是O(m)總復(fù)雜度為O(n^2 * m)。500^2 * 500等于1.25 * 10^8在C的優(yōu)化下已經(jīng)可以在1到2秒內(nèi)穩(wěn)定跑完。這也是這道題設(shè)計上的精妙之處它考察的正是降維思維的工程價值。2. 算法設(shè)計細(xì)節(jié)2.1 前綴和預(yù)處理行方向還是列方向要想在固定上下邊界后快速獲得每一列的和需要提前構(gòu)建前綴和數(shù)組。通常有兩種選擇。第一種是sum[i][j]表示第j列前i行的元素和這樣第k列在上下邊界top和bottom之間的和可以直接用sum[bottom][k] - sum[top-1][k]計算。第二種是構(gòu)建行的前綴和再按列壓縮。我在實際做題時更習(xí)慣用第一種列方向的前綴和因為固定上下邊界后我需要頻繁按列取區(qū)間和。用colSum[i][j]表示第j列前i行的累計和代碼上就是for (int j 1; j m; j) { for (int i 1; i n; i) { colSum[i][j] colSum[i-1][j] matrix[i][j]; } }這樣后續(xù)壓縮數(shù)組時只需一行代碼temp[k] colSum[bottom][k] - colSum[top-1][k];前綴和的意義不只是減少計算量它還能讓代碼邏輯更清晰。colSum數(shù)組直接表達(dá)了“從第top行到第bottom行第k列的總和”不需要再寫內(nèi)層循環(huán)臨時累加避免了不少低效操作。2.2 枚舉上邊界與下邊界枚舉上下邊界是二維降維的第一步。需要注意的是上下邊界的組合一共有n * (n1) / 2種因為上邊界可以是從第1行到第n行的任意一行下邊界必須大于等于上邊界。有的同學(xué)會習(xí)慣寫成for (int top 1; top n; top) { for (int bottom top; bottom n; bottom) { // 處理當(dāng)前上下邊界 } }這里有個容易忽略的細(xì)節(jié)當(dāng)top等于bottom時意味著子陣只有一行此時它退化成一維最大子段和問題。這種情形也必須覆蓋否則會漏解。而枚舉過程中這個情形天然被包含在內(nèi)不需要單獨寫特殊判斷。這是枚舉寫法的一個好處不需要為“單行子陣”單獨編碼。我自己的習(xí)慣是在內(nèi)層循環(huán)里先初始化temp數(shù)組把當(dāng)前上下邊界下每一列的和算好然后再去跑一維DP。每更換一組上下邊界temp數(shù)組都會被重新計算這是整個算法最核心的循環(huán)體。2.3 動態(tài)規(guī)劃求解壓縮后的一維數(shù)組拿到temp數(shù)組之后就要用一維最大子段和的思路找出當(dāng)前上下邊界下的最優(yōu)左右區(qū)間。這里的DP實現(xiàn)可以不用額外開數(shù)組用滾動變量就行int cur 0; int best INT_MIN; for (int k 1; k m; k) { cur max(temp[k], cur temp[k]); best max(best, cur); }這段代碼看起來很簡潔但里面藏著一個關(guān)鍵細(xì)節(jié)cur的初值。我見過很多初次接觸這道題的同學(xué)把cur初始化為0這在一維最大子段和的某些寫法中可以工作但在二維場景下會引入一個隱蔽的bug——當(dāng)整個temp數(shù)組全是負(fù)數(shù)時cur永遠(yuǎn)加不出正確的最大值因為cur從0開始max(temp[k], cur temp[k])會把每個負(fù)數(shù)都被0“拉”回來最終可能算出一個不存在的“空子陣”答案0。正確的做法是把cur初始化為0但配合best取INT_MIN或者在一開始的cur max(temp[k], cur temp[k])中保證第一項參與比較。我用的是把best設(shè)為INT_MIN這樣即使矩陣全為負(fù)數(shù)最終答案也是一塊真實存在的最小子陣而不是虛構(gòu)的0。2.4 復(fù)雜度分析這套算法的時間復(fù)雜度可以這樣拆解構(gòu)建列前綴和數(shù)組O(n * m)。枚舉上下邊界O(n^2)組。每組邊界內(nèi)計算temp數(shù)組O(m)。每組邊界內(nèi)跑一維DPO(m)?？傮w復(fù)雜度為O(n^2 * m n * m)主導(dǎo)項是O(n^2 * m)。空間復(fù)雜度為O(n * m)用于存儲矩陣和前綴和數(shù)組。以n500、m500為例最內(nèi)層的計算量約為1.25 * 10^8次操作C在開啟O2優(yōu)化后完全能跑進(jìn)1到2秒。對比暴力四重枚舉的10^10級別這個優(yōu)化帶來的提升是數(shù)量級的也是競賽中最看重的部分。3. C代碼實現(xiàn)與關(guān)鍵注釋3.1 完整可運行代碼下面給出可直接提交的完整代碼我用的是C11標(biāo)準(zhǔn)適配藍(lán)橋杯的常見編譯環(huán)境。#include iostream #include algorithm #include climits using namespace std; const int MAXN 505; int matrix[MAXN][MAXN]; int colSum[MAXN][MAXN]; int temp[MAXN]; int main() { int n, m; cin n m; for (int i 1; i n; i) { for (int j 1; j m; j) { cin matrix[i][j]; } } // 構(gòu)建列方向前綴和colSum[i][j]表示第j列前i行的和 for (int j 1; j m; j) { for (int i 1; i n; i) { colSum[i][j] colSum[i-1][j] matrix[i][j]; } } int ans INT_MIN; // 枚舉上邊界 for (int top 1; top n; top) { // 枚舉下邊界 for (int bottom top; bottom n; bottom) { // 當(dāng)前上下邊界下將每列的和壓縮到temp數(shù)組中 for (int k 1; k m; k) { temp[k] colSum[bottom][k] - colSum[top-1][k]; } // 對temp數(shù)組跑一維最大子段和 int cur 0; for (int k 1; k m; k) { cur max(temp[k], cur temp[k]); ans max(ans, cur); } } } cout ans endl; return 0; }這段代碼沒有冗余的函數(shù)封裝所有邏輯都在main函數(shù)中順序展開。對于競賽環(huán)境來說這反而是更穩(wěn)妥的寫法可以避免函數(shù)調(diào)用的潛在開銷也讓調(diào)試時更容易定位變量問題。3.2 關(guān)鍵變量設(shè)計思路三個數(shù)組各司其職matrix[MAXN][MAXN]存儲原始矩陣。下標(biāo)從1開始而不是0是為了讓前綴和的定義更自然colSum[i-1][j]在下標(biāo)為0時自動取到0不需要額外初始化邊界。colSum[MAXN][MAXN]存儲列方向前綴和。colSum[i][j]表示第j列前i行所有元素的和。這樣設(shè)計是因為在枚舉上下邊界時我需要的是“第k列從top到bottom的和”用兩個前綴和相減即可得到。temp[MAXN]是每次枚舉上下邊界時生成的臨時數(shù)組長度等于列數(shù)m用于承載降維后的一維數(shù)組。使用全局?jǐn)?shù)組能自動初始化為0也避免了在棧上開大數(shù)組導(dǎo)致棧溢出。MAXN取505是因為藍(lán)橋杯的常見數(shù)據(jù)范圍在500左右多留一點余量防止越界。3.3 邊界條件和數(shù)據(jù)類型的經(jīng)驗之談這道題有兩個邊界細(xì)節(jié)需要特別注意第一是負(fù)數(shù)處理。題目并沒有保證矩陣元素全為正數(shù)所以初始答案ans不能設(shè)為0。如果矩陣中所有元素都是負(fù)數(shù)正確答案應(yīng)該是這些負(fù)數(shù)中最大的那個而如果把ans初值設(shè)為0程序會錯誤地輸出0相當(dāng)于虛構(gòu)了一個不存在的空子陣。解決方案有兩種一是用INT_MIN初始化ans二是用-INF大負(fù)數(shù)代替。我習(xí)慣用INT_MIN因為它語義清楚也方便與max配合使用。第二是求和結(jié)果可能超過int范圍。當(dāng)n和m達(dá)到500元素絕對值達(dá)到1000時整個矩陣的和可能達(dá)到2.5 * 10^8雖然int能裝下但為了避免極端數(shù)據(jù)下的溢出風(fēng)險穩(wěn)妥的做法是把累加變量設(shè)為long long。我在訓(xùn)練時吃過這個虧所以現(xiàn)在只要題目沒限制元素大小就默認(rèn)用long long處理累加。如果改用long long只需把數(shù)組類型和ans、cur的類型統(tǒng)一修改即可邏輯不變。3.4 測試樣例驗證用幾個典型樣例來驗證代碼正確性。樣例1常規(guī)正負(fù)混合3 3 1 -1 2 -1 2 -1 2 -1 1模擬可得最大子陣正好覆蓋了所有正數(shù)答案為5。樣例2矩陣全為負(fù)數(shù)2 2 -1 -2 -3 -4最大子陣是單個元素-1答案應(yīng)當(dāng)為-1。此時ans初始化INT_MIN的作用就體現(xiàn)出來cur在第一個元素時取max(-1, 0 (-1))等于-1ans更新為-1。如果初值設(shè)0這里就會輸出0。樣例3單行矩陣1 5 2 -1 3 -2 4這等價于一維最大子段和問題最大子段為2-13-24答案為6。這些樣例跑通后代碼基本就沒有邏輯問題。剩余的風(fēng)險主要來自性能邊界和極端數(shù)據(jù)規(guī)模這兩個方面在下一節(jié)細(xì)講。4. 常見問題與調(diào)試心得4.1 全負(fù)數(shù)矩陣的隱藏陷阱這個問題我在前文提到過但值得單獨拿出來再強調(diào)一次因為它實在太容易踩了。很多教程里寫一維最大子段和時會給出一個初值dp[0] 0的寫法。這個寫法在一維版本下配合“答案初始化為第一個元素”可以工作但如果直接搬到二維代碼里把ans初始化為0就會出現(xiàn)一個嚴(yán)重的邏輯漏洞。我調(diào)試過一位同學(xué)的代碼他的思路是用ans max(ans, cur)逐輪更新但ans初值設(shè)成了0。測試正負(fù)數(shù)混合的樣例全都能過偏偏遇到“全為負(fù)數(shù)”的邊界樣例時輸出永遠(yuǎn)是0而不是真實的最大負(fù)數(shù)。這類問題在比賽中極難發(fā)現(xiàn)因為常規(guī)隨機測試數(shù)據(jù)幾乎必然包含正數(shù)不會觸發(fā)這個bug。建議在寫完這道題后手動測一組全負(fù)數(shù)數(shù)據(jù)這是最直接的驗證方式。4.2 初始化與INF選擇的經(jīng)驗關(guān)于INT_MIN和自定義大負(fù)數(shù)的選擇我來說說自己的偏好。INT_MIN是climits頭文件中定義的常量含義是int類型的最小值直接用它可以少寫一個#define或const int INF -0x3f3f3f3f。自定義大負(fù)數(shù)-0x3f3f3f3f在競賽圈中也很流行原因是它不會溢出且和INT_MIN相比在做加法時不會出現(xiàn)極端下溢。但在本題中cur temp[k]用的cur是從0開始的不會直接用INT_MIN參與加法所以用INT_MIN初始化ans是安全的。如果用了long long版本建議用LLONG_MIN初始化或者用-4e18這類自定義大負(fù)數(shù)。我個人習(xí)慣是直接寫LLONG_MIN因為C標(biāo)準(zhǔn)庫已經(jīng)提供了定義不需要自己拼數(shù)字。4.3 數(shù)組越界與循環(huán)邊界細(xì)節(jié)由于題目給定的下標(biāo)范圍是1到n和1到m數(shù)組要開到至少MAXN n 5的余量。有些同學(xué)習(xí)慣把數(shù)組開得剛剛好比如矩陣是[n][m]在競賽中可能遇到數(shù)組訪問越界到非法內(nèi)存導(dǎo)致莫名其妙的結(jié)果錯誤。我見過一種典型越界場景在構(gòu)建colSum時內(nèi)層循環(huán)從1到n外層循環(huán)從1到m這是正確的但如果把兩個循環(huán)的順序反了并且前綴和更新時寫成了colSum[i][j] colSum[i-1][j] matrix[i][j]那么由于colSum[i-1][j]在使用時依賴于前一行的數(shù)據(jù)必須確保第i-1行已經(jīng)計算完畢。用列優(yōu)先遍歷可以保證這一點但如果用行優(yōu)先就要注意前綴和更新公式的寫法否則會取到未初始化的垃圾值。另一個容易出錯的點是上下邊界枚舉中的top-1。當(dāng)top1時top-10此時colSum[0][k]應(yīng)該是0。因為全局?jǐn)?shù)組默認(rèn)初始化為0所以這個訪問是安全的。但如果你把數(shù)組開成局部變量并忘記初始化這里就會出現(xiàn)隨機值。這也是我建議用全局?jǐn)?shù)組的原因之一。4.4 進(jìn)階變形環(huán)形矩陣與更大數(shù)據(jù)范圍理解最大子陣的降維思路后可以順手拓展幾個相似問題這有助于加深對算法的理解。常見的變形是環(huán)形最大子陣即矩陣的行和列可以循環(huán)跨越邊界。通常的解法是把矩陣復(fù)制一倍變成2n乘2m的新矩陣然后在新矩陣上限制子陣大小不超過n和m再跑最大子陣算法。這需要額外維護(hù)“子陣寬度和高度的限制”也就需要在DP過程中判定區(qū)間長度不能直接套用基礎(chǔ)版代碼。另一個變形是數(shù)據(jù)范圍擴大后的優(yōu)化比如n1000、m1000時O(n^2 * m)達(dá)到了10^9級別直接跑會超時。這時可以把內(nèi)外層循環(huán)調(diào)整固定列邊界而不是行邊界讓復(fù)雜度變?yōu)镺(m^2 * n)選擇較小的維度作為被平方的維度可以有效降低常數(shù)。這些變形本質(zhì)上都在利用“固定一個維度壓縮另一個維度”的思想把它吃透了遇到任何矩陣類的子區(qū)域問題都能更快找到切入點。5. 我個人在實際做題中的一點體會最大子陣這道題我第一次接觸時也走了一些彎路。當(dāng)時第一反應(yīng)是四重枚舉加二維前綴和覺得能算出來就行結(jié)果一提交就超時。后來靜下心去看一維最大子段和的代碼才意識到固定上下邊界這個操作才是整個題目的關(guān)鍵開關(guān)它讓問題從“找矩形”變成了“找一維區(qū)間”難度一下子降低了一個級別。從那以后我遇到二維區(qū)間最值問題都會先問自己一句能不能先固定一個方向把問題壓成一維。這個思維習(xí)慣幫我解決了不少類似的競賽題比如最大子矩陣的變種、帶權(quán)矩陣的最優(yōu)區(qū)域劃分等。最后再分享一個小技巧刷這類動態(tài)規(guī)劃題時不要只盯著標(biāo)準(zhǔn)解法看建議自己先寫一版暴力解再用小數(shù)據(jù)對比優(yōu)化解的輸出確保兩者完全一致。這樣既能驗證正確性也能讓你對優(yōu)化的價值有更直觀的體會。最大子陣作為藍(lán)橋杯歷屆試題中的經(jīng)典題考察的不僅是動態(tài)規(guī)劃更是那種“把復(fù)雜問題簡化成已知問題”的工程直覺值得反復(fù)琢磨。