描述

给定一个由正整数和负整数组成的二维数组，子矩形是位于整个数组内的任意连续子数组，其大小为\(1\times1\)或更大。矩形的和是该矩形中所有元素的总和。在这个问题中，具有最大和的子矩形被称为最大子矩形。

例如，对于数组：

\(0\) \(-2\) \(-7\) \(0\)

\(9\) \(2\) \(-6\) \(2\)

\(-4\) \(1\) \(-4\) \(1\)

\(-1\) \(8\) \(0\) \(-2\)

最大子矩形位于左下角：

\(9\) \(2\)

\(-4\) \(1\)

\(-1\) \(8\)

并且其和为\(15\)。

输入由一个\(N\times N\)的整数数组组成。输入首先是单独一行的单个正整数\(N\)，表示这个正方形二维数组的大小。接着是\(N^2\)个由空格分隔的整数。这些是数组中的\(N^2\)个整数，按行优先顺序给出。也就是说，先给出第一行的所有数字，从左到右，然后是第二行的所有数字，从左到右，以此类推。\(N\)最大可以是\(100\)。数组中的数字范围在\([-127,127]\)内。

输出最大子矩形的和。

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

15

来源

大纽约 2001