Q-6-5. 二維最大子矩陣


提交答案

分數: 100 (部分)
時間限制: 0.3s
記憶體限制: 1G

作者:
題目類型

輸入一個 \( m*n \) 的二維整數矩陣 \( A[1:m][1:n]\) ,要找一塊總和最大的連續子矩陣,輸出其總和。 以下圖為例,挑選 \( A[1:3][2:3] \) 可以獲得最大總和 \( 13 \) 。

 2 -2  3  3
-6  5  2 -8
 3  7 -2  4

 

輸入格式

第一行有兩個正整數 \( m \) 與 \( n \) 。 接下來 \( m \) 行每行 \( n \) 個整數,代表矩陣由上而下由左而右的內容。 \( m \) 與 \( n \) 皆不超過 \( 200 \) ,矩陣內的數字絕對值皆不超過 \( 1e4 \) 。

輸出格式

子矩陣的最大可能總和,子矩陣邊長可為 \(0\)。

範例輸入 1

3 4
2 -2 3 3
-6 5 2 -8
3 7 -2 4

範例輸出 1

13

範例輸入 2

1 6
-2 1 3 -1 4 -5

範例輸出 2

7

留言

目前沒有評論。