编程之美2.15——子数组之和的最大值

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

解法：
先计算出以左上角的元素(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)时间内计算出整体之和）。
[cpp]
#include <iostream> 
#include <algorithm> 
using namespace std; 
 
#define MAXN 1003 
int A[MAXN][MAXN]; 
long long PS[MAXN][MAXN]; 
 
inline long 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<=n; j++) 
            PS[i][j] = A[i][j]+PS[i-1][j]+PS[i][j-1]-PS[i-1][j-1]; 
    int a, c; 
    long long All = A[1][1]; 
    for (a=1; a<=n; a++) 
        for (c=a; c<=n; c++) 
        { 
            // 将子矩阵上下边界设为第a行和第c行，在这些子矩阵中取最大值 
            long long Tail = MatrixSum(a, 1, c, 1); 
            for (j=2; j<=n; j++) 
            { 
                Tail = max(MatrixSum(a, j, c, j),  
                    MatrixSum(a, j, c, j)+Tail);  
                All = max(Tail, All); 
            } 
        } 
    cout << All; 
} 

 作者：linyunzju