To The Max
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
Source:
Submit