问题 4330 --最大子矩阵和

4330: 最大子矩阵和★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 191  解决: 138
[提交][状态][命题人:]

题目描述

求一个n*n的矩阵的最大子矩阵和。
 比如在如下这个矩阵中:
0 -2 -7 0
9  2 -6 2
-4 1 -4 1
-1 8 0 -2 
拥有最大和的子矩阵为:
9 2
-4 1
-1 8

其和为15。

若矩阵中所有的数均为负数,则最大子矩阵和为0。

输入

一个n*n的矩阵。输入的第1行给出n(0<n<=100)。后面跟有n行数据,每行含有n个整数,每个整数间使用空格分隔。

输出

最大子矩阵和。
样例输入
Copy
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
样例输出
Copy
15

提示

来源

 

[提交][状态]