二维数组求子数组中最大的和

    上次的课堂编程题目是一维数组中子数组的和，现在难度加大了不少，二维数组需要考虑的方面很多，这个程序我是在上个课堂题目基础上加以改善完成的，核心代码如下：

int maxSubArray(int a[], int n)

{

    assert(a!=NULL && n>0);

    int cur = 0;

    int max = INF;

 

    for(int i=0; i<n; i++)

    {

        cur += a[i];

 

        //当cur小于0时，应该重新开始计数.

        if(cur < 0)

            cur = 0;

 

        if(cur > max)

            max = cur;

    }

    return max;

}

 

int findMaxSubMatrix(int a[][N], int n)

{

    int tmpSum[N];

    int max = INF;

 

    //枚举所有行的可能组合。

    for(int i=0; i<n; i++)

    {

        //将tmpSum清零。

        memset(tmpSum,0,sizeof(tmpSum));

        for(int j=i; j<n; j++)

        {

            //加上当前行的元素。

            for(int k=0; k<n; k++)

                tmpSum[k] += a[j][k];

            int tmpMax = maxSubArray(tmpSum, n);

            if(tmpMax > max)

                max = tmpMax;

 

        }

    }

    return max;

}

 

int main()

{

    int a[N][N];

    int n = 0;

 

    while(cin>>n && n)

    {

        for(int i=0; i<n; i++)

            for(int j=0; j<n; j++)

                cin>>a[i][j];

        cout<<findMaxSubMatrix(a, n)<<endl;

    }

     

    return 0;

}

程序运行结果截图：