8373: DP10 最大子矩阵
[Creator : ]
Description
已知矩阵的大小定义为矩阵中所有元素的和。
给定一个矩阵，你的任务是找到最大的非空（大小至少是 1 * 1）子矩阵。
比如，如下 4 * 4 的矩阵
的最大子矩阵是
这个子矩阵的大小是15。
给定一个矩阵，你的任务是找到最大的非空（大小至少是 1 * 1）子矩阵。
比如，如下 4 * 4 的矩阵
0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2
的最大子矩阵是
9 2 -4 1 -1 8
这个子矩阵的大小是15。
Input
输入是一个 N * N 的矩阵。
输入的第一行给出 $N\ (0 < N \leq 100)$。
再后面的若干行中，依次（首先从左到右给出第一行的 N 个整数，再从左到右给出第二行的 N 个整数……）给出矩阵中的 $N^2$ 个整数，整数之间由空白字符分隔（空格或者空行）。
已知矩阵中整数的范围都在 [-127, 127]。
输入的第一行给出 $N\ (0 < N \leq 100)$。
再后面的若干行中，依次（首先从左到右给出第一行的 N 个整数，再从左到右给出第二行的 N 个整数……）给出矩阵中的 $N^2$ 个整数，整数之间由空白字符分隔（空格或者空行）。
已知矩阵中整数的范围都在 [-127, 127]。
Output
输出最大子矩阵的大小。
Sample 1 Input
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
Sample 1 Output
15
Sample 2 Input
5
-93 -35 -126 -28 -87
48 22 63 126 -23
-17 23 28 89 45
-4 -92 -44 97 -26
-1 -14 9 61 14
Sample 2 Output
439
Sample 3 Input
10
-42 -109 -77 -116 105 -113 56 -68 26 69
-82 -66 95 -70 -119 120 -15 77 -55 58
-69 115 53 -107 35 110 111 -94 -124 106
-12 -81 -123 -110 -81 121 -89 101 -67 122
-66 -10 30 110 36 67 -46 -114 95 -14
33 -81 13 2 41 64 -57 -55 98 79
80 -38 23 -103 79 13 53 -62 -46 105
-47 -51 -34 14 62 -37 -33 -19 -68 78
-84 -30 102 -23 -27 -115 16 -22 -11 -15
-89 -37 -1 -75 -57 -7 -26 28 -93 121
Sample 3 Output
728
HINT
相同题目：牛客网。