Problem E: 最大子矩阵

上一题 正确率: $17.44\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $86$ 正确数量 $15$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划 递推

Description

给定一个二维数组，一个子矩形是一个大小为1 x 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

第一行输入一个正整数N，表示正方形二维数组的大小。接下来是由空格(空格和换行)分隔的N行N列的整数。这些是数组的N^2个整数，以行主顺序表示。也就是说，第一行的所有数，从左到右，然后第二行中的所有数，从左到右，等等，N最大可能是100。数组中的数字将在[-127,127]范围内。

Output

输出最大子矩阵的和

Sample Input复制

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

Sample Output复制

15

提示

多组