#include<stdio.h>
#define N 110

int maxof(int a, int b);
int line(int i, int l, int r, int matrix[N][N]);

int main()
{
    int n;
    int matrix[N][N];
    int sum[N][N][N];
    int i, j, l, r;
    int max;
    scanf("%d", &n);
    for(i = 1; i <= n; i ++)
        for(j = 1; j <= n; j ++)
            scanf("%d", &matrix[i][j]);
    for(l = 1; l <= n; l ++)
        for(r = l; r <= n; r ++)
            sum[0][l][r] = 0;
    max = -128;
    for(i = 1; i <= n; i ++)
        for(l = 1; l <= n; l ++)
            for(r = l; r <= n; r ++)
                if((sum[i][l][r] = maxof(sum[i - 1][l][r] + line(i, l, r, matrix), line(i, l, r, matrix))) > max)
                    max = sum[i][l][r];
    printf("%d\n", max);
    return 0;
}

int maxof(int a, int b)
{
    return a > b ? a : b;
}

int line(int i, int l, int r, int matrix[N][N])
{
    int sum = 0;
    for(; l <= r; l ++)
        sum += matrix[i][l];
    return sum;
}
/*
二维的最大子序列和问题
sum[i][l][r] = max{sum[i - 1][l][r] + line(i, l, r), line(i, l, r)}
sum[i][l][r]是以矩阵第i行第l至r列元素为底的最大矩阵和
line(i, l, r)是矩阵第i行第l至r列元素和
*/

• Re:最大子序列和问题，直接转化到二维 (4) Neolyo 2011-11-30 15:13:13