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

题目

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;
}

第 5 空应填（ ）

答案

rowsum[i][last]-rowsum[i][first-1]

题解

考点定位

本题（最大矩阵和第⑤空）考「列区间和累加」,对应大纲 4.2.1 前缀和（难度【3】）。

解题过程

⑤处行 i 在 [first,last] 列的和：

``cpp area += rowsum[i][last] - rowsum[i][first-1]; ``

答案：rowsum[i][last]−rowsum[i][first−1]。

易错提醒

① 与普及组同题；② O(n²m) 总复杂度由三重循环列对+行构成。