结对测试二（求二维数组的子数组之和最大值）（兰梦、刘佳琪）

题目：

求二维数组（矩阵）的子矩阵之和的最大值。

算法思想

以第一元素a[1][1]为基准点，

先计算出以左上角的元素(1,1)和当前元素(i,j)为顶点对的子矩阵的部分和，部分和的计算如下

PS[i][j] = A[i][j]+PS[i-1][j]+PS[i][j-1]-PS[i-1][j-1]

把问题从二维转化为一维以提高算法性能。

假设已经确定了矩阵区域的上下边界，不如知道矩阵区域的上下边界分布是第a行和第c行，接下来要确定左右边界。

我们把第a行和第c行之间的每一列看成一个整体，相当于一维数组中的一个元素（通过子矩阵部分和可以在O(1)时间内计算出整体之和）。

#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1003
int A[MAXN][MAXN];
long PS[MAXN][MAXN];

inline  long MatrixSum(int s, int t, int i, int j)
{
    return PS[i][j]-PS[i][t-1]-PS[s-1][j]+PS[s-1][t-1];
}

int main()
{
    int m, n, i, j;
    cin >> n >> m;
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
            cin >> A[i][j];
    for (i=0; i<=n; i++)
        PS[i][0] = 0;
    for (j=0; j<=m; j++)
        PS[0][j] = 0;
    // 计算矩阵的部分和
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
            PS[i][j] = A[i][j]+PS[i-1][j]+PS[i][j-1]-PS[i-1][j-1];
    int a, c;
     long All = A[1][1];
    for (a=1; a<=n; a++)
        for (c=a; c<=n; c++)
        {
            // 将子矩阵上下边界设为第a行和第c行，在这些子矩阵中取最大值
            long Tail = MatrixSum(a, 1, c, 1);
            for (j=2; j<=m; j++)
            {
                int t=MatrixSum(a, j, c, j);
                if (Tail>0)
                    Tail=Tail+t;
                else
                    Tail=t;
                if(Tail>All)
                    All=Tail;
            }
        }
    cout << All;
    return 0;
}

运行截图