ssl 1205 최대 하위 매트릭스와

Description
N[2<=N<=100]을 주고 N*N의 행렬을 제시한다. 행렬의 수는 [-127127] 사이이다.행렬 중 하위 행렬의 최대 합을 구하십시오.
예를 들면 다음과 같습니다.
0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2
가장 큰 하위 행렬은 다음과 같습니다.
9 2 -4 1 -1 8
그것의 합은 15이다.
Input
Output
Sample Input
4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -18 0 -2
Sample Output
15
Hint
zju
분석: 접두사와 dp를 미리 처리한 다음에 dp로 하면 됩니다.코드:

var
      a,b:array [0..101,0..101] of longint;
      ans,max,i,j,n,k:longint;
begin
      readln(n);
        for i:=1 to n do
            for j:=1 to n do read(a[i,j]);
          max:=-maxlongint;
          for i:=1 to n do
            for j:=1 to n do b[i,j]:=a[i,j]+b[i,j-1];
             for i:=1 to n do
              for j:=i to n do
               begin
                    ans:=0;
                    for k:=1 to n do
                     begin
                          ans:=ans+b[k,j]-b[k,i-1];
                          if ans>max then max:=ans;
                          if ans<0 then ans:=0;
                     end;
               end;
       writeln(max);
end.