Q-6-5. 二維最大子矩陣
輸入一個 \( 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
留言