最大子矩阵问题实例解析
问题：
求一个M*N的矩阵的最大子矩阵和。
比如在如下这个矩阵中：
0-2-70 92-62 -41-41 -180-2
拥有最大和的子矩阵为：
92 -41 -18
其和为15。
思路：
首先，这个子矩阵可以是任意大小的，而且起始点也可以在任何地方，所以，要把最大子矩阵找出来，我们要考虑多种情况。
假定原始矩阵的行数为M，那么对于子矩阵，它的行数可以是1到M的任何一个数，而且，对于一个K行（K<M）的子矩阵，它的第一行可以是原始矩阵的第1行到M-K+1的任意一行。
例子：
对于上面的矩阵，如果子矩阵的行数是2，那么它可以是下面几个矩阵的子矩阵：
0-2-70 92-62
或者
92-62 -41-41
或者
-41-41 -180-2
在每一种情况里（我们这里有三种），我们还要找出一个最大的子矩阵，当然，这只是一种情况的最大子矩阵（局部最大），不一定是global最大。但是，如果我们知道每一种情况的最大，要找出global最大，那就小菜一碟儿了。
在讲在一个特殊情况下求最大子矩阵之前，先讲一个事实：
假设这个最大子矩阵的维数是一维，要找出最大子矩阵,原理与求“最大子段和问题”是一样的。最大子段和问题的递推公式是b[j]=max{b[j-1]+a[j],a[j]}，b[j]指的是从0开始到j的最大子段和。
Java实现示例：
假设原始矩阵为：[9， 2，-6， 2]，那么b[]={9,11,5,7},那么最大字段和为11，如果找最大子矩阵的话，那么这个子矩阵是[9，2]
求最大子段和的代码如下：
publicintmaxSubsequence(int[]array){
if(array.length==0){
return0;
}
intmax=Integer.MIN_VALUE;
int[]maxSub=newint[array.length];
maxSub[0]=array[0];
for(inti=1;i<array.length;i++){
maxSub[i]=(maxSub[i-1]>0)?(maxSub[i-1]+array[i]):array[i];
if(max<maxSub[i]){
max=maxSub[i];
}
}
returnmax;
}
但是，原始矩阵可以是二维的。假设原始矩阵是一个3*n的矩阵，那么它的子矩阵可以是1*k,2*k,3*k，（1<=k<=n）。如果是1*K，这里有3种情况：子矩阵在第一行，子矩阵在第二行，子矩阵在第三行。如果是2*k，这里有两种情况，子矩阵在第一、二行，子矩阵在第二、三行。如果是3*k，只有一种情况。
为了能够找出最大的子矩阵，我们需要考虑所有的情况。假设这个子矩阵是2*k,也就是说它只有两行，要找出最大子矩阵，我们要从左到右不断的遍历才能找出在这种情况下的最大子矩阵。如果我们把这两行上下相加，情况就和求“最大子段和问题”又是一样的了。
为了找出在原始矩阵里的最大子矩阵，我们要遍历所有的子矩阵的可能情况，也就是说，我们要考虑这个子矩阵有可能只有1行，2行，。。。到n行。而在每一种情况下，我们都要把它所对应的矩阵部分上下相加才求最大子矩阵（局部）。
比如，假设子矩阵是一个3*k的矩阵，而且，它的一行是原始矩阵的第二行，那么，我们就要在
92-62 -41-41 -180-2
里找最大的子矩阵。
如果把它上下相加，我们就变成了4,11,-10,1，从这个数列里可以看出，在这种情况下，最大子矩阵是一个3*2的矩阵，最大和是15.
为了能够在原始矩阵里很快得到从i行到j行的上下值之和，我们这里用到了一个辅助矩阵，它是原始矩阵从上到下加下来的。
假设原始矩阵是matrix,它每一层上下相加后得到的矩阵是total，那么我们可以通过如下代码实现：
int[][]total=matrix;
for(inti=1;i<matrix[0].length;i++){
for(intj=0;j<matrix.length;j++){
total[i][j]+=total[i-1][j];
}
}
如果我们要求第i行到第j行之间上下值的和，我们可以通过total[j][k]-total[i-1][k]得到,k的范围从1到matrix[0].length-1。
有了这些知识点，我们只需要在所有的情况下，把它们所对应的局部最大子矩阵进行比较，就可以得到全局最大的子矩阵。代码如下：
publicintsubMaxMatrix(int[][]matrix){
int[][]total=matrix;
for(inti=1;i<matrix[0].length;i++){
for(intj=0;j<matrix.length;j++){
total[i][j]+=total[i-1][j];
}
}
intmaximum=Integer.MIN_VALUE;
for(inti=0;i<matrix.length;i++){
for(intj=i;j<matrix.length;j++){
//result保存的是从i行到第j行所对应的矩阵上下值的和
int[]result=newint[matrix[0].length];
for(intf=0;f<matrix[0].length;f++){
if(i==0){
result[f]=total[j][f];
}else{
result[f]=total[j][f]-total[i-1][f];
}
}
intmaximal=maxSubsequence(result);
if(maximal>maximum){
maximum=maximal;
}
}
}
returnmaximum;
}
C语言相关的实现
题目
题目描述：
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1*1)子矩阵。
比如，如下4*4的矩阵
0-2-70 92-62 -41-41 -180-2
的最大子矩阵是
92 -41 -18
这个子矩阵的大小是15。
输入：
输入是一个N*N的矩阵。输入的第一行给出N(0<N<=100)。
再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。
已知矩阵中整数的范围都在[-127,127]。
输出：
测试数据可能有多组，对于每组测试数据，输出最大子矩阵的大小。
样例输入：
4
0-2-70
92-62
-41-4 1
-18 0-2
样例输出：
15
AC代码
#include<stdio.h>
#include<stdlib.h>
intmain(void)
{
inti,j,h,k,n,max,sum,cur,matrix[101][101];
while(scanf("%d",&n)!=EOF){
//初始化接收矩阵
for(i=0;i<n;i++){
for(j=0;j<n;j++)
scanf("%d",*(matrix+i)+j);
}
//动态规划(类似于一维数组连续最大子序列和)
max=matrix[0][0];
for(i=0;i<n;i++){
//i，j确定上下界
for(j=i;j<n;j++){
//初始化
for(k=i,sum=0;k<=j;k++)
sum+=matrix[k][0];
if(sum>max)
max=sum;
for(h=1;h<n;h++){
for(k=i,cur=0;k<=j;k++)
cur+=matrix[k][h];
if(sum>=0)
sum+=cur;
else
sum=cur;
if(sum>max)max=sum;
}
}
}
printf("%d\n",max);
}
return0;
}