给出一个N [2<=N<=100]，并给出一个N*N的矩阵，矩阵中的数为[-127,127]之间。求出矩阵中一块子矩阵的最大和。

比如：

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

和最大的子矩阵应该是这个：

9 2
-4 1
-1 8

它的和是15。

Example

Input

4


0 -2 -7 0

9 2 -6 2


-4 1 -4 1

-18 0 -2


Output

15


数据：
http://www.hysbz.com/zybbs/viewFile.asp?Boardid=28&ID=536


76 2005-10-26 19:59:30 00:00.03 440K FPC Tango

我也不知道是不是DP了，我说说我的方法

先从简单的说起，假如是只有一个数列，求最大连续的和的话，很多人都会，其实就是用sum从头加到尾，假如某个时候sum<0就sum:=0;因为假如前面的总和是负数就倒不如不加在这一行上面了

例如0 -2 -7 0 9 2 -6 2

sum=0 -2 -7 0 9 11 5 7

看明白了吗？……就是说只要sum变成了负数下一个sum就变成0，原因上面写了，所以最大和就是11

那么就好办了，假设st[i,j]代表第j列从1到第i个数的总和，

那么枚举2行for i:=1 to n do ,for j:=i to n do

那么只要把中间那一截数字的和看成一个数，就是f[k]:=st[j,k]-st[i-1,k]

所以方法就和单列最大和的一样了

我的程序很慢……

不要取笑





var
  i,j,k,n,a,b:integer;
  max,sum:longint;
  f:array[0..100,0..100]of integer;
begin
    readln(n);
    a:=1;
    b:=0;
    fillchar(f,sizeof(f),0);
    while (a-1)*n+b<sqr(n) do begin
        inc(b);
        if b>n then begin
            inc(a);
            b:=b mod n;
        end;
        read(k);
        f[a,b]:=f[a-1,b]+k;
    end;

    max:=-maxlongint;
    for i:=1 to n do begin
        for j:=i to n do begin
            sum:=0;
            for k:=1 to n do begin
                sum:=sum+f[j,k]-f[i-1,k];
                if sum>max then max:=sum;
                if sum<0 then sum:=0;
            end;
        end;
    end;
    writeln(max);
end.


我说了是做了以后假如sum为负下一个才变成0

例如 -1 -2 -3 -4 -5 -6

f(就是以i结尾这个数形成的列最大的和): -1 -2 -3 -4 -5 -6

sum:-1-->0-->-2-->0-->-3-->0-->-4-->0-->-5-->0

sum是这样子变化的