问题：给定m*n的矩阵，求具有最大和的矩形子数组。

先上暴力算法，求出所有矩形子数组的和，记录其中最大值。思路就是从1*1的最小子矩阵开始(m*n个)，到m*n的最大子矩阵(一个)结束，求出每个子矩阵的和，找出最大值。

[cpp]
/** @brief 在m*n的矩阵a中查找最大子矩阵的和
** @note 使用一维数组代替二维数组,
** 元素a[i][j] = a[i*n+j].
** @return 最大子数组的和
** @author quickSort,
** @date 2013/08/10
**
*/
int maxSubMatrix_BF(int *a, int m, int n)
{
int mm=NM,sum=0;
for(int i=0;i {
for(int j=0;j {///for all a[i][j]
for(int ii=i;ii {
for(int jj=j;jj {
sum = 0;
for(int ti=i; ti<=ii;ti++)
for(int tj=j; tj<=jj;tj++)
{
sum += a[ti*n+tj];///a[ii][jj] ///sum of a[i][j] -> a[ii][jj]
}
mm = max(sum,mm);
}
}
}
}
cout<<__FUNCTION__<<": "< return m;
}

/** @brief 在m*n的矩阵a中查找最大子矩阵的和
** @note 使用一维数组代替二维数组,
** 元素a[i][j] = a[i*n+j].
** @return 最大子数组的和
** @author quickSort,
** @date 2013/08/10
**
*/
int maxSubMatrix_BF(int *a, int m, int n)
{
int mm=NM,sum=0;
for(int i=0;i {
for(int j=0;j {///for all a[i][j]
for(int ii=i;ii {
for(int jj=j;jj {
sum = 0;
for(int ti=i; ti<=ii;ti++)
for(int tj=j; tj<=jj;tj++)
{
sum += a[ti*n+tj];///a[ii][jj] ///sum of a[i][j] -> a[ii][jj]
}
mm = max(sum,mm);
}
}
}
}
cout<<__FUNCTION__<<": "< return m;
}

为了使矩形的2维都可以是变量，这里使用一维数组模拟二维矩阵，m*n的矩阵中元素a[i][j]对应于数组中的值就是a[i*n+j]。
其复杂度是多少呢……？一眼看去，6个for循环，OMG。。。像是O(m3n3).
显然，复杂度太高了。。。。

===================================================================================================
结合一维最大子数组，可以这么考虑：二维矩阵在某种程度上可以看做一位数组，而一维数组的每个元素又是一维数组。对于一维数组，最大子数组的和我们已经可以在O(n)内求出，而不需要O(n2)。

这里再回忆一下这两个算法：

平方算法：
[cpp]
///算法1.
///在数组a[n]中找出子数组的最大和
void maxSum_1(int a[], int n)
{
int sum=NM,m=NM;//NM是一个很小的负数，例如-99999999.下同
for(int i=0; i {
sum=0;
for(int j=i; j {
sum += a[j];
m = max(m,sum);
}
}
cout<<__FUNCTION__<<" : "< }

///算法1.
///在数组a[n]中找出子数组的最大和
void maxSum_1(int a[], int n)
{
int sum=NM,m=NM;//NM是一个很小的负数，例如-99999999.下同
for(int i=0; i {
sum=0;
for(int j=i; j {
sum += a[j];
m = max(m,sum);
}
}
cout<<__FUNCTION__<<" : "< }
扫描算法：

[cpp]
///算法2，扫描算法
///在数组a[n]中找出子数组的最大和
void maxSum_3(int a[], int n)
{
int maxSoFar=NM, maxEndingHere=NM;
for(int i=0; i {
maxEndingHere = max(maxEndingHere+a[i], a[i]);
maxSoFar = max(maxSoFar,maxEndingHere);
}
cout<<__FUNCTION__<<" : "<< maxSoFar < }

///算法2，扫描算法
///在数组a[n]中找出子数组的最大和
void maxSum_3(int a[], int n)
{
int maxSoFar=NM, maxEndingHere=NM;
for(int i=0; i {
maxEndingHere = max(maxEndingHere+a[i], a[i]);
maxSoFar = max(maxSoFar,maxEndingHere);
}
cout<<__FUNCTION__<<" : "<< maxSoFar < }