1768:最大子矩阵
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。
比如，如下4 * 4的矩阵
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
的最大子矩阵是
9 2
-4 1
-1 8
这个子矩阵的大小是15。 - 输入
- 输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N 2个整数，整数之间由空白字符分隔（空格或者空行）。已知矩阵中整数的范围都在[-127, 127]。
- 输出
- 输出最大子矩阵的大小。
- 样例输入
-
4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2
- 样例输出
-
15
- 来源
- 翻译自 Greater New York 2001 的试题
分析：
先对每一行计算前缀和数组，用于方便地计算每一行指定段的元素之和。
然后枚举子矩阵的起始列first、结束列last。然后在这个区域计算列数为last-first+1的所有子矩阵的最大和。（计算过程类似一维矩阵的最大子段和。）
1 #include <stdio.h> 2 const int SIZE = 100; 3 int matrix[SIZE + 1][SIZE + 1]; 4 int rowsum[SIZE + 1][SIZE + 1]; //rowsum[i][j]记录第 i 行前 j 个数的和 5 int m, n, i, j, first, last, area, ans; 6 int main() 7 { 8 scanf("%d",&n); 9 m=n; 10 for (i = 1; i <= m; i++) 11 for (j = 1; j <= n; j++) 12 scanf("%d", &matrix[i][j]); 13 ans = matrix[1][1]; 14 for (i = 1; i <= m; i++) 15 rowsum[i][0]=0; 16 for (i = 1; i <= m; i++) 17 for (j = 1; j <= n; j++) 18 rowsum[i][j] = rowsum[i][j-1]+matrix[i][j]; 19 for (first = 1; first <= n; first++) 20 for (last = first; last <= n; last++) 21 { 22 area=0; 23 for (i = 1; i <= m; i++) 24 { 25 area += rowsum[i][last] -rowsum[i][first-1]; 26 if (area > ans) ans = area; 27 if (area < 0) area = 0; 28 } 29 } 30 printf("%d\n", ans); 31 return 0; 32 }
