NOIP 提高 2014 第一轮 第 33 题：完善程序（双栈模拟数组）第 2 空

题目

2.（最大矩阵和）给出 $M$ 行 $N$ 列的整数矩阵，就最大的子矩阵和（子矩阵不能为空）。

输入第一行包含两个整数 $M$ 和 $N$，即矩阵的行数和列数。之后 $M$ 行，每行 $N$ 个整数，描述整个矩阵。程序最终输出最大的子矩阵和。（第一空 $2$ 分，其余 $3$ 分，共 $14$ 分）

#include <stdio.h>
const int SIZE=100;
int matrix[SIZE+1][SIZE+1];
int rowsum[SIZE+1][SIZE+1];    //rowsum[i][j]记录第i行前j个数的和
int m,n,i,j,first,last,area,ans;
int main(){
   scanf(“%d %d”,&m,&n);
   for(i=1;i<=m;i++)
      for(j=1;j<=n;j++)
         scanf(“%d”,&matrix[i][j]);
ans=matrix     (1)     ;
for(i=1;i<=m;i++)
         (2)      ;
  for(i=1;i<=m;i++)
     for(j=1;j<=n;j++)
         rowsum[i][j]=     (3)     ;
  for(first=1;first<=n;first++)
     for(last=first;last<=n;last++){
             (4)     ;
       for(i=1;i<=m;i++){
           area+=     (5)     ;
           if(area>ans)
             ans=area;
           if(area<0)
             area=0;
       }
     }
  printf(“%d\n”,ans);
  return 0;
}

第 2 空应填（ ）

答案

rowsum[i][0]=0

题解

考点定位

本题（最大矩阵和第②空）考「前缀和边界」,对应大纲 4.2.1 前缀和（难度【2】）。

解题过程

②处：

``cpp rowsum[i][0] = 0; ``

答案：rowsum[i][0]=0。

易错提醒

① 与普及组同题；② 差分查询依赖 0 位哨兵。