POJ #1050

Looks quite intuitive at the very first sight... I thought:
rect[x, y, w+1, h+1] = rect[x, y, w, h] + num[x + w + 1, y..y+h+1] + num[x..x+w+1, y+h+1] - num[x+w+1, y+h+1]

But that results in O(n^4) at least. 

Reference: http://blog.csdn.net/hitwhylz/article/details/11848439. Lesson learnt: usually 2D issue can be converted to 1D problem to solve. Cool thought. And what is more important: decoding problem thoroughly and identify familiar pattern in disguise from it.

Here is my AC code:

//    1050
//    Ref:    http://blog.csdn.net/hitwhylz/article/details/11848439

#include <stdio.h>

#define MAX_N 100
#define Max(a, b) (a) > (b) ? (a) : (b)

int max_sum_1D(int rowSum[MAX_N + 1], int n)
{
    //    dp[i] = max{a[i], dp[i-1] + a[i]}
    int ret = -2147483648;
    int dp[MAX_N + 1] = { 0 };
    for (int k = 1; k <= n; k ++)
    {
        dp[k] = Max(rowSum[k], dp[k-1] + rowSum[k]);
        ret = Max(ret, dp[k]);
    }
    return ret;
}

int calc(int in[MAX_N + 1][MAX_N + 1], unsigned n)
{
    int maxSum = -2147483648;

    for (int i = 1; i <= n; i++)
    {
        int rowSum[MAX_N + 1] = { 0 };    // for compact

        for (int j = i; j <= n; j++)    // Row[i]..Row[j]
        {
            //    Compact to 1D array, from row[i] to row[j] for each column
            for (int k = 1; k <= n; k++)
            {
                rowSum[k] += in[j][k];
            }

            int tmp_sum = max_sum_1D(rowSum, n);
            maxSum = Max(tmp_sum, maxSum);
        }
    }

    return maxSum;
}

int main()
{
    int n; scanf("%d", &n);
    int in[MAX_N + 1][MAX_N + 1];
    
    //    Get input
    for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= n; j++)
    {
        scanf("%d", &(in[i][j]));
    }

    //
    int ret = calc(in, n);
    printf("%d
", ret);
    
    return 0;
}