问题 1133 --最大子阵和

1133: 最大子阵和

时间限制: 1 Sec  内存限制: 32 MB
提交: 226  解决: 27
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][4440kb]

题目描述

有一个包含正数和负数的二维数组。一个子矩阵是指在该二维数组里,任意相邻的下标是1*1或更大的子数组。一个子矩阵的和是指该子矩阵中所有元素的和。本题中,把具有最大和的子矩阵称为最大子矩阵。
例如:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
这个数组的最大子矩阵为:
9 2
-4 1
-1 8
其和为15。

输入

输入包含多组测试数据。每组输入的第一行是一个正整数N(1<=N<=100),表示二维方阵的大小。接下来N行每行输入N个整数,表示数组元素,范围为[-127,127]。

输出

输出最大子阵和。

样例输入

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

样例输出

15

提示

来源

[提交][状态]