TopCoder

Thumb 1
羽瀨川小鷹
我是布丁

User's AC Ratio

100.0% (38/38)

Submission's AC Ratio

80.5% (62/77)

Tags

Description

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

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

Input Format

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

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

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

Output Format

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

Sample Input

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

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 (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1