d073: Q-6-5. 二維最大子矩陣
Tags : DP
Accepted rate : 65人/68人 ( 96% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-09-23 21:31

Content

輸入一個 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

Input

第一行有兩個正整數 m 與 n。接下來 m 行每行 n 個整數,代表矩陣由上而

下由左而右的內容。m 與 n 皆不超過 200,矩陣內的數字絕對值皆不超過 1e4。

Output

子矩陣的最大可能總和。

Sample Input
//case 1
3 4
2 -2 3 3
-6 5 2 -8
3 7 -2 4
//case 2
1 6
-2 1 3 -1 4 -5
Sample Output
//case 1
13
//case 2
7
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (16%): 1.0s , <1M
不公開 測資點#1 (16%): 1.0s , <1M
不公開 測資點#2 (17%): 1.0s , <1M
不公開 測資點#3 (17%): 1.0s , <1M
不公開 測資點#4 (17%): 1.0s , <1M
不公開 測資點#5 (17%): 1.0s , <1M
Hint :
Tags:
DP
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」