【POJ 1050】To the Max

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 105;
const int INF = 0x7fffffff;
int best;
int rowsum[MAXN][MAXN];
int sum[MAXN];
int n;
int ans;

int main()
{
    scanf("%d", &n);
    memset(rowsum, 0, sizeof(rowsum));
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            scanf("%d", &rowsum[i][j]);
            rowsum[i][j] += rowsum[i][j - 1];
        }
    }
    ans = -INF;
    sum[0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j)
        {
            best = 0;
            for (int k = 1; k <= n; ++k)
            {
                sum[k] = rowsum[k][j] - rowsum[k][i - 1] + sum[k - 1]; /* 压缩 */
                ans = max(ans, sum[k] - sum[best]);
                if (sum[best] > sum[k]) best = k;
            }
        }
    printf("%d\n", ans);
    return 0;
}