Problem 108 Maximum Sum，解子矩陣最大總和

題目說來短短的，在一個矩陣中，找一個包含於其中小矩陣，這個小矩陣中的和是最大的。

剛開始，我用了暴力法，從頭到尾，所有可能的小矩形都給他算一下，這樣就一定可以找出哪個矩形的和最小。可是上傳後，居然是超過時間(TLE)，所以這個題目是故意讓你想點辦法來解決的。

我也想不到，看看他網站的提示，原來要建立sum[i][j] 的矩陣，以減少未來計算總和的需求。在後面，如果要計算 R[i][j]到 R[x][y]的矩形的和，只要算

sum[x][y] - sum[i-1][y] - sum[x][j-1] + sum[i-1][j-1];

就行了。

最後完成上傳時，還出現小插曲，有runtime error，原來是宣告short所造成。真是的，幹麻省這一點點記憶體。

p108 問題連結
ACM 題庫目錄
回到首頁