【题目描述】

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是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数组求的是二维数组的前缀和。后面求最大字段和除了借鉴前面的思想还可以借助下面的过程：

1. 初始状态是二维数组（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）

也就是下面这样

但是，实际上，上面的代码是三重循环，也就是上图中，所有绿色的点都要执行最内部的一遍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

这个时候实际上是第二列，因为减法减去了第一列的值

......