uva_108 - Maximum Sum

[cpp] 
/**
 *  首先計算每一列的前序和（即0行到所有行上值的總和）
 *  其次，最大的子矩陣一定在a行和b行之間，所以我們可以枚舉所有的可能組合，時間復雜度為O(N*N)
 *  因為我們在第一步中計算了前序和，那麼第二步中a行和b行之間的子矩陣可以看成一個一維的數組，長度為N。
 *  其值的計算可以利用第一步中的前序和，遍歷所有列，讓0-b的總和減去0-a的總和，即為a-b的總和。
 *  利用該算法算出該一維數組中的最大連續子序列。時間復雜度為O(N)，
 *  找出最大值，最後的時間復雜度為0(N*N*N)。
*/ 
#include <cstdio> 
#include <algorithm> 
 
using namespace std; 
 
#define MAX 101 
#define INF 0x7fffffff 
 
int array[MAX][MAX];        //矩陣數據 
int arraySum[MAX][MAX+1];     //矩陣前序和 
int tmp[MAX];               //臨時一維數組 
int n;                      //矩陣大小 
 
/*
該算法十分簡單，maxSum表示最終的最大值，currentMaxSum表示當前的最大值，只需要遍歷數組一遍即可找出最大值。
*/ 
int findMaxinum(){ 
    int maxSum = -INF, currentMax = 0; 
    for(int i=0; i<n; i++){ 
        currentMax += tmp[i]; 
        if(currentMax < 0) {currentMax = 0; continue;} 
        maxSum = max(maxSum, currentMax); 
    } 
    return maxSum; 
} 
 
int main(){ 
    scanf("%d",&n); 
    for(int i=0; i<n; i++) 
        for(int j=0; j<n; j++) 
            scanf("%d",&array[i][j]); 
             
    //計算前序和，i表示列，j表示最終行，總和為0-j上的所有值 
    for(int i=0; i<n; i++) 
        for(int j=1; j<=n; j++) 
            arraySum[i][j] = arraySum[i][j-1] + array[i][j-1]; 
 
    int maxinum = -INF; 
    //遍歷所有a，b的組合 
    for(int i=0; i<n; i++){ 
        for(int j=i+1; j<=n; j++){ 
            //計算臨時一維數組 
            for(int x=0; x<n; x++){ 
                tmp[x] = arraySum[x][j]-arraySum[x][i]; 
            } 
            maxinum = max(maxinum, findMaxinum()); 
        } 
    } 
 
    printf("%d\n",maxinum); 
    return 0; 
}