最大子矩阵和问题

这是最大子段和的扩展！  所以可以将二维的转化成一维的求解！！

#include <iostream>
using namespace std;

const int M=4;
const int N=3;

int (int n,int *a);
int MaxSum2(int m,int n,int a[M][N]);

int main()
{
    int a[][N] = {{4,-2,9},{-1,3,8},{-6,7,6},{0,9,-5}};

    for(int i=0; i<M; i++)
    {
        for(int j=0; j<N; j++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }

    cout<<endl;
    cout<<"数组a的最大连续子段和为:"<<MaxSum2(M,N,a)<<endl;

    return 0;
}

int MaxSum2(int m,int n,int a[M][N])
{
    int sum = 0;
    int *b = new int[n+1];
    for(int i=0; i<m; i++)
    {
        for(int k=0; k<n;k++)
        {
            b[k]=0;
        }

        for(int j=i;j<m;j++)//枚举初始行i,结束行j
        {
            for(int k=0; k<n; k++)
            {
                b[k] += a[j][k];//b[k]为纵向列之和  将i 到 j行的转为一行然后求解就行！！！
                int max = MaxSum(n,b);
                if(max>sum)
                {
                    sum = max;
                }
            }
        }
    }
    return sum;
}
int (int n,int *a) //这是一维的字段和(dp) b[j]=max{b[j-1]+a[j],a[j]},1<=j<=n。
{
    int sum=0,b=0;
    for(int i=1; i<=n; i++)
    {
        if(b>0)  b+=a[i];
        else  b=a[i];
        if(b>sum)
            sum = b;
    }
    return sum;
}