二次元累積和を使う

wa.py

# board[n][n] があるとする
table = [[0 for _ in xrange(N)] for _ in xrange(N)]

for c in xrange(N):
    for r in xrange(N):
        total = 0
        if c != 0:
            total += table[c - 1][r]
        if r != 0:
            total += table[c][r - 1]
        if c != 0 and r != 0:
            total -= table[c - 1][r - 1]
        table[c][r] = total + board[c][r]

maximum = 0
for t in xrange(N):
    for b in xrange(t + 1):
        for r in xrange(N):
            for l in xrange(r + 1):
                cost = table[t][r]
                if b != 0:
                    cost -= table[b - 1][r]
                if l != 0:
                    cost -= table[t][l - 1]
                if b != 0 and l != 0:
                    cost += table[b - 1][l - 1]

                maximum = max(maximum, cost)