NOIP 提高组初赛 · NOIP 2014 提高组初赛试题 第 28 题

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

这题核心是把二维问题降成一维：枚举左右列边界，用行前缀和 O(1) 算出每行区间和，再对这一行序列跑 Kadane 求最大子段和。填空就按这个流程，先初始化 ans 和 rowsum 边界，再递推行前缀和，最后每轮重置 area 并减去正确的起始前缀。

最容易栽跟头的是 ans 初始值写 0，一旦矩阵全负就会错过正确答案；rowsum[i][0] 不初始化成 0，后面求区间和就会带进垃圾值；area 在每对 first/last 里没重置为 0，导致累加越算越大；还有区间和公式写错成 rowsum[i][first] 而不是 rowsum[i][first-1]，结果多或少了一列。这些坑在考试里都是送分题，但扣起来很疼。

这道题考查的是最大子矩阵和，本质是把二维枚举压缩成一维最大子段和（Kadane），中间用到行前缀和来 O(1) 求任意列区间的和。命题人喜欢在这里挖坑：全负矩阵时 ans 不能初值 0；前缀和数组下标从 1 开始，第 0 列必须手动置 0；枚举左右边界时 area 要每轮清零；区间和公式里的 first-1 容易写错。考频上，二维数组相关题目在题库里共出现过 29 题，覆盖 GESP 四级到 NOIP 提高组初赛等多个级别，2026 年考得最密（9 题），2014 年也出过 2 题，说明这类‘降维 + 前缀和’的组合是高频考点。前缀和本身单独考过 2 题，简单动态规划（含 Kadane）考了 94 题，2023-2026 年更是爆发式增长，2026 年单年 13 题，可见命题趋势是越来越爱把一维 DP 嵌套到二维场景里。再来看历年趋势，2014 年这道题属于 NOIP 提高组初赛，当时只考了 1 题前缀和、1 题简单 DP，现在回头看，这种组合题在近年普及组和提高组里都更常见了，尤其是 GESP 六级、七级里大量出现类似‘压缩维度 + 区间和’的套路。所以预测未来几年，NOIP 提高组初赛大概率还会继续考这类题，形式可能是‘最大子矩形和’‘带权最大子矩阵’或者‘三维压缩成二维再 Kadane’，难度会维持在 O(n^2*m) 或 O(m*n^2) 的枚举边界，关键还是看你是否能熟练写出前缀和递推和 Kadane 的 area 重置。回到代码填空，我们按流程走：

1. ans 的初值：因为矩阵可能全负，ans 不能是 0，必须初始化为第一个元素 matrix[1][1]，这样即使后面所有区间和都是负的，也能正确返回最大的那个负数。所以 (1) 填 [1][1]。

2. 行前缀和数组 rowsum[i][j] 表示第 i 行前 j 列的和。递推式是 rowsum[i][j] = rowsum[i][j-1] + matrix[i][j]。但数组下标从 1 开始，递推时 j=1 会用到 rowsum[i][0]，这个位置必须手动初始化为 0，否则就是垃圾值。因此 (2) 填 rowsum[i][0]=0。

3. 递推计算 rowsum 数组，显然 (3) 填 rowsum[i][j-1] + matrix[i][j]。

4. 枚举左右列边界 first 和 last，对每一对边界，我们要对每一行求区间和并 Kadane。Kadane 的经典写法是维护当前和 area，每轮 new first/last 时 area 必须清零，否则上一轮累加会污染这一轮。所以 (4) 填 area=0。

5. 第 i 行在[first,last]列的区间和，利用前缀和就是 rowsum[i][last] - rowsum[i][first-1]。这里最容易错写成 rowsum[i][first]，那样会多减或少减一列。因此 (5) 填 rowsum[i][last]-rowsum[i][first-1]。

把这些填进去，整个算法的主线就清晰了：先预处理行前缀和，再双重枚举左右列，内层对每一行做 Kadane，不断更新全局最大 ans。时间复杂度是 O(n^2*m)，空间 O(m*n)，完全符合题目要求。最后输出 ans 即可。