最大子矩阵
题目描述
有一个包含正数和负数的二维矩阵。矩阵的和是指矩阵中所有元素的和。现在给定一个这样的矩阵,求出一个子矩阵使得子矩阵的和最大,并输出最大值。例如矩阵:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
和最大的子矩阵为:
9 2
-4 1
-1 8
和为 15 是该矩阵中和最大的子矩阵
输入描述
输入第一行为一个 NN 表示矩阵的行数和列数。接下来有 NN 行,每行 NN 个数,代表矩阵的元素. 1 \leq N \leq 801≤N≤80 , 并且每一个元素都在 [−127,127] 的区间中
输出描述
最大子矩阵的和
样例输入
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
样例输出
15
要多组输入输出