【题解】最大子矩阵
【题目描述】
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是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个整数……)给出矩阵中的N2个整数，整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[−127,127]。
【输出描述】
输出最大子矩阵的大小。
【样例输入】
4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2
【样例输出】
15
【题目分析】
二维数组其实可以看做一维数组
需要用到 最大字段和 的知识
我们处理二维数组，按照行的数据进行处理，按列求出最大值。
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
scanf("%d",&jz[i][j]);
jz[i][j]+=jz[i][j-1];
}那么，jz数组求出来以后的结果是：
0 -2 -9 -9 9 11 5 7 -4 -3 -7 -6 -1 7 7 5
可以看出，上面的结论是按照行数据，每一个数都是这一行的前面几个数的求和。
【参考代码】
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int jz[105][105]={0};
int main()
{
int n,i,j;
scanf("%d",&n);
//求二维数组的前缀和
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
scanf("%d",&jz[i][j]);
jz[i][j]+=jz[i][j-1];
}
int sum,max=-1000000000;
//最大字段和的思想
for(i=1;i<=n;i++)
for(j=i;j<=n;j++){
sum=0;
for(int k=1;k<=n;k++){
sum+=jz[k][j]-jz[k][i-1];
if(sum>max)
max=sum;
if(sum<0)
sum=0;
}
}
printf("%d\n",max);
return 0;
}上面的代码中 ，jz数组求的是二维数组的前缀和。后面求最大字段和除了借鉴前面的思想还可以借助下面的过程：
初始状态是二维数组（i表示行，j表示列）
j=1 j=2 j=3 j=4 i=1 1,1 1,2 1,3 1,4 i=2 2,1 2,2 2,3 2,4 i=3 3,1 3,2 3,3 3,4 i=4 4,1 4,2 4,3 4,4
当i=1时，我们可以访问（1，1），（1，2），（1，3）（1，4）
当i=2时，我们可以访问（2，2），（2，3），（2，4）
当i=3时，我们可以访问（3，3），（3，4）
当i=4时，我们可以访问（4，4）
也就是下面这样
| j=1 | j=2 | j=3 | j=4 | |
| i=1 | 1,1 | 1,2 | 1,3 | 1,4 |
| i=2 | 2,1 | 2,2 | 2,3 | 2,4 |
| i=3 | 3,1 | 3,2 | 3,3 | 3,4 |
| i=4 | 4,1 | 4,2 | 4,3 | 4,4 |
但是，实际上，上面的代码是三重循环，也就是上图中，所有绿色的点都要执行最内部的一遍for循环。
比如，当(i,j)=(1,1)时，这时最内层循环看jz[k][j]和jz[k][i-1]的变化关系是
k j - k i-1 1 1 1 0 2 1 2 0 3 1 3 0 4 1 4 0
这相当于二维数组中第一列每一个数都判断了一遍最大值。
......
当(i,j)=(1,2)时，，这时内层循环看jz[k][i]和 jz[k][i-1]的变化关系是
k j - k i-1 1 2 1 0 2 2 2 0 3 2 3 0 4 2 4 0
因为jz数组存的是和的关系。这个地方表示是前两列，每个数相比的最大值。
......
当(i,j)=(2,2)时，，这时内层循环看jz[k][i]和 jz[k][i-1]的变化关系是
k j - k i-1 1 2 1 1 2 2 2 1 3 2 3 1 4 2 4 1
这个时候实际上是第二列，因为减法减去了第一列的值
......
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。