Problem
Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1 x 1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.
As an example, the maximal sub-rectangle of the array:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
is in the lower left corner:
9 2
-4 1
-1 8
and has a sum of 15.
The input consists of an N x N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N 2 integers separated by whitespace (spaces and newlines). These are the N 2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].
Output
Output the sum of the maximal sub-rectangle.
Example
Input
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
Output
15
【参考程序】:
var a,s:array[0..100,0..100]of int64;
n,i,j,k,x1,y1,x2:longint;
max,m:int64;
begin
while not eof do
begin
read(n);
if n=0 then break;
for i:=1 to n do
for j:=1 to n do
read(a[i,j]);
for i:=0 to n do
begin
s[0,i]:=0;
s[i,0]:=0;
end;
for x1:=1 to n do
for y1:=1 to n do
s[x1,y1]:=a[x1,y1]+s[x1,y1-1];//计算好S矩阵，方便下面计算
max:=-maxlongint;
for x1:=1 to n do
for x2:=x1 to n do
begin
m:=s[1,x2]-s[1,x1-1];
if m>max then max:=m;
for k:=2 to n do
begin
if m>0 then m:=m+s[k,x2]-s[k,x1-1]//大于０就累加起来
else m:=s[k,x2]-s[k,x1-1];//小于０就是展现自己，如果加了上面的m会使我还小．
if m>max then max:=m;
end;
end;
writeln(max);
end;
end.