#include
#include
#include
///
/** @brief 矩形子数组的最大和 完整测试代码
** @author quickSort,
** @date 2013/08/10
**
**
*/

using namespace std;

int d[] = {-3,-2,-67,-7,-9,-8};
int c[] = {1,-2,3,10,-4,7,2,-5};
int e[] = /// 2*8 || 4*4
{ 1,-2, 3,10,
-4, 7, 2,-5,
1,-8,-5,-9,
7,10,-6,-20
};
const int NM = -99999;

void maxSum_1(int a[], int n)
{
int sum=NM,m=NM;
for(int i=0; i {
sum=0;
for(int j=i; j {
sum += a[j];
m = max(m,sum);
}
}
cout<<__FUNCTION__<<" : "< }

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 < }

template
inline T abs(T n)
{
return n<0 (-n):n;
}

///-----------------------------------------
/** @brief 在m*n的矩阵a中查找最大子矩阵的和
** @note 使用一维数组代替二维数组,
** 元素a[i][j] = a[i*n+j].
** @return 最大子数组的和
** @author quickSort,
** @date 2013/08/10
**
*/
int maxSubMatrix(int *a, int m, int n)
{
int i,j,k;
int maxSoFar=NM,maxEndingHere;
int *sum = (int*)malloc(sizeof(int)*n);
for(i=0;i {
memset(sum,0,sizeof(int)*n);///sum=0
for(j=i;j {
maxEndingHere = 0;
for(k=0;k {
sum[k] += a[j*n+k];///a[j*n+k]=a[j][k]
maxEndingHere=max(maxEndingHere+sum[k],sum[k]);
maxSoFar = max(maxSoFar,maxEndingHere);
}
}
}
free(sum);
cout<<__FUNCTION__<<" : "< return maxSoFar;
}
/** @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;
}

int main()
{
int n = sizeof(c)/sizeof(int);
int a[100];
reset(a,n);
maxSum_1(a,n);

maxSum_3(a,n);

maxSubMatrix(e,4,4);
maxSubMatrix_BF(e,4,4);
return 0;
}

结果：
[plain]

maxSum_1 : 18
maxSum_3 : 18
maxSubMatrix : 17
maxSubMatrix_BF: 17


Process returned 0 (0x0) execution time : 0.296 s
Press any key to continue.

maxSum_1 : 18
maxSum_3 : 18
maxSubMatrix : 17
maxSubMatrix_BF: 17

Process returned 0 (0x0) execution time : 0.296 s
Press any key to continue.