1733 . 最大二維子矩陣

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

98.6% (68/69)

Submission's AC Ratio

77.2% (105/136)

Tags

Description

給你一個填滿整數的二維陣列，"子矩陣總和"的定義就是任取其中一個長方形，裡面所有數字的總和。
現在給你這個二維矩陣，請問最大可能的"子矩陣總和"是多少呢？

不過請注意，至少要選一個數字，不能選一個"空的"子矩陣!!

Input Format

輸入有多組測試資料!! 以EOF作為結尾。

每組測試資料第一行有兩個整數 rn, cn 代表二維矩陣有幾橫排，幾直排
接下來 rn 行總共有 rn*cn 個數，是這個二維陣列中的數字

rn, cn <= 50
你可以假設所有數字的絕對值總和不會超過 int 大小

Output Format

請輸出一個數，代表子矩陣可能的最大總和

Sample Input 1

2 5
1 0 4 -1 7
2 -9 -3 2 2
3 3
1 1 1
1 1 1
1 1 1
1 1
-1

Sample Output 1

11
9
-1

Hints

2015/7/28 測資修復，感謝青い猫

Problem Source

原TIOJ1733 / kelvin

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
Submit
Back to Top