[软件工程学习笔记]结对作业---二维数组求最大子矩阵

#include <iostream>  
using namespace std;    
#define N 5  
#define M 4  
  
int Sum(int (*PSum)[M+1],int istart,int iend,int j) //istart--iend第j列的和  
{  
    int pSum;  
    pSum=PSum[iend][j]-PSum[istart-1][j]-PSum[iend][j-1]+PSum[istart-1][j-1];  
    return pSum;  
}  
  
//求二维数组的连续子数组之和的最大值  
int MaxSum(int (*a)[M])  
{  
    int PSum[N+1][M+1];  
    int i,j;  
    for(i=0;i<=N;i++)  
        PSum[i][0]=0;  
    for(j=0;j<=M;j++)  
        PSum[0][j]=0;  
    for(i=1;i<=N;i++)  
        for(j=1;j<=M;j++)  
            PSum[i][j]=PSum[i-1][j]+PSum[i][j-1]-PSum[i-1][j-1]+a[i-1][j-1];  
    int MaxSum=INT_MIN;  
    int Start,All;  
    int istart,iend;  
    for(istart=1;istart<=N;istart++)  
    {  
        for(iend=istart;iend<=N;iend++)  
        {  
            Start=Sum(PSum,istart,iend,M);  
            All=Sum(PSum,istart,iend,M);  
            for(j=M-1;j>=1;j--)  
            {  
                if(Start>0)  
                    Start+=Sum(PSum,istart,iend,j);  
                else  
                    Start=Sum(PSum,istart,iend,j);  
                if(Start>All)  
                    All=Start;  
            }  
            if(All>MaxSum)  
                MaxSum=All;  
        }  
    }  
    return MaxSum;  
}  
  
  
int main()  
{  
   int a[N][M]={  
        1,2,3,8,  
        4,0,-2,11,  
        -8,2,2,2,  
        9,3,-4,5,
        5,4,-4,3
    }; 
    int maxSum=MaxSum(a); 
    cout<<maxSum<<endl;  
    getchar();  
  
    return 0;  
}