TopCoder

Thumb output jddoia
$\huge 南ことり$
今天也要輸贏!?

User's AC Ratio

100.0% (24/24)

Submission's AC Ratio

76.7% (46/60)

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

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144