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; 
}