To The Max

Time Limit
1s
Memory Limit
32768KB
Judge Program
Standard
Ratio(Solve/Submit)
43.75%(14/32)
Description:

给定一个整数型的二维数组,从这个二维数组中找出一个子矩形,子矩形的大小为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。

Input:

测试数据有多组。输入整数T,表示有T组测试数据。每组测试数据,输入n,代表n*n的矩形。接下来n行每行输入n个整数。n<=100。


Output:

每组测试数据输出一行答案,为最大子矩阵的总和。

Sample Input:
1
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
Sample Output:
15

Submit