题目描述

ACM队员们到Z镇游玩，Z镇是一个很特别的城镇，它有m+1条东西方向和n+1条南北方向的道路，划分成M*N个区域。Z镇的名胜位于这些区域内，从上往下第i行，从左往右数第j列的区域记为D（i,j）。ACM队员们预先对这M*N个区域打分V(i,j)(分数可正可负)。分数越高表示他们越想到那个地方，越低表示他们越不想去。为了方便集合，队员们只能在某一个范围内活动。我们可以用(m1,n1)与(m2,n2)(m1<=m2，n1<=n2)表示这样一个范围：它是这些区域的集合： ，ACM队员希望他们活动区域的分值总和最大。
当然，有的队员可能一个也不去（例如，所有区域的分值都是负数。当然，如果某范围内的分值和为0的话，他们也不会去玩）。也有可能他们游览整个Z镇。你的任务是编写一个程序，求出他们的活动范围(m1,n1),(m2,n2)。

输入

输入有m+1行，第一行有两个整数m,n（m,n定义如上）。其中( )，接下来的m行，每行n个整数，第i行第j个数表示分数V(i,j)。（-128<=v(i,j)<=127）每两个整数之间有一个空格。

输出

输入只一行，分两种情况：
1． 队员在范围内(m1,n2)(m2,n2)内活动，输出该范围内的分值。
2． 队员们任何地方都不去，只需输出NO。
注意：不要输出多余的空行，行首行尾不要有多余的空格。

思路

枚举行m1,m2，在行m1,m2之间的元素中，把同一列的元素加起来（即把二维压缩成一维），然后用最大子序列的方法求解，就是做n多边最大子序列，就可以枚举到每一种情况。

var
  a:array[-10..1000,-10..1000] of longint;
  f,p:array[-10..1000] of longint;
  i,j,k,n,m,s,x,y,max:longint;
begin
  readln(n,m);
  max:=-1000;
  for i:=1 to n do
    begin
      for j:=1 to m do
        read(a[i,j]);
      readln;
    end;

  for i:=1 to n do
    begin
      fillchar(f,sizeof(f),0);
      for j:=1 to m do p[j]:=a[i,j];
      for j:=1 to m do
        begin
          if p[j]+f[j-1]>=0 then begin f[j]:=p[j]+f[j-1]; if max<f[j] then max:=f[j]; end
                            else f[j]:=0;
        end;
      fillchar(f,sizeof(f),0);
      for j:=i+1 to n do
        begin
          for k:=1 to m do
            p[k]:=p[k]+a[j,k];
          for k:=1 to m do
            if p[k]+f[k-1]>=0 then begin f[k]:=p[k]+f[k-1]; if max<f[k] then max:=f[k]; end
                              else f[k]:=0;
        end;
    end;
  if max<=0 then writeln('NO') else
  writeln(max);
end.