Problem2813--最大子矩阵

2813: 最大子矩阵

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。
例如，给出如下4*4的矩阵：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
最大子矩阵是：
9 2
-4 1
-1 8
这个子矩阵的大小是15

Input

第一行，一个整数N，表示接下来是N*N的矩阵（0＜N≤300）
接下来N行，每行N个元素，给出N*N的矩阵，矩阵中整数的范围是[-127,127]

Output

一行，一个整数，输出最大子矩阵的大小

Sample Input Copy 

4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

Sample Output Copy 

15

Source/Category

动态规划 NOI level5 
[Submit] [Status]