题目：求二维数组（矩阵）的子矩阵之和的最大值。
把问题从二维转化为一维。假设已经确定了矩阵区域的上下边界，不如知道矩阵区域的上下边界分布是第a行和第c行，接下来要确定左右边界。
我们把第a行和第c行之间的每一列看成一个整体，相当于一维数组中的一个元素。即求BC[1]、BC[2]、BC[3]、.。。、BC[M]中和最大的一段。
BC[i]= B[a][i] + .......+ B[c][i]。
枚举矩形的上下边界，再用一维情况下的方法确定左右边界。就可以得到二维问题的解。时间复杂度：O（N^2 * M）
Example：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
最大子矩阵为：
9 2
-4 1
-1 8
输出：15
二维情况下，定义部分和：PS[i][j] 等于以（1，1）、（i，1）、（1，j）、（i，j）为顶点的矩形区域的元素之和。
在O（1）的时间可以得到更小的部分和：PS[i][j] = PS[i][j-1] + PS[i-1][j] - PS[i-1][j-1] + A[i][j]
程序如下：
#include<iostream>
using namespace std;
#define max(a,b) (((a)>=(b))?(a):(b))
int BC(int **PS,int a,int c,int i)
{
return PS[c][i]-PS[c][i-1]-PS[a-1][i]+PS[a-1][i-1];
}
int main()
{
int Start,All;
int m,n;
int i,j;
int **PS;
int **A;
int a,c;
int maxnum=-1;
cout<<"请输入行数：";
cin>>n;
cout<<"请输入列数：";
cin>>m;
PS=(int **)malloc(sizeof(int*)*(n+1));
A=(int **)malloc(sizeof(int*)*(n+1));
for (i=0;i<=n;i++)
{
PS[i]=(int *)malloc(sizeof(int)*(m+1));
A[i]=(int *)malloc(sizeof(int)*(m+1));
}
cout<<"请输入"<<n<<"行"<<m<<"列数字："<<endl;
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
{
cin>>A[i][j];
}
}
//求部分和
for (i=0;i<=n;i++)
{
PS[i][0]=0;
}
for (j=0;j<=m;j++)
{
PS[0][j]=0;
}
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
{
PS[i][j]=A[i][j]+PS[i][j-1]+PS[i-1][j]-PS[i-1][j-1];
}
}
//枚举求出问题的解
for (a=1;a<=n;a++)
{
for (c=a;c<=n;c++)
{
Start=BC(PS,a,c,m);
All=BC(PS,a,c,m);
for (i=m-1;i>=1;i--)
{
Start=max(BC(PS,a,c,i),BC(PS,a,c,i)+Start);
All=max(Start,All);
if (All>maxnum)
{
maxnum=All;
}
}
}
}
cout<<maxnum<<endl;
return 0;
}