編程之美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