PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
This problem can be solved by combining bruteforce and dynamic programming (DP):

At first, we find all nonempty submatrices, for each we call its two opposite vertices (x1, y1) and (x2, y2) respectively. Then your task is finding the maximal sum of the respective Oregion. To do it, we must find the nonempty submatrix in range (x1 + 1, y1 + 1)…(x2  1, y2  1) which has the minimal value to remove. This minimal sum can be found by DP this way:

We define F(i, j, k, t) as the minimal sum of a submatrix appearing in range (i, j)…(k, t), it should be calculated by Min{F(i + 1, j, k, t), F(i, j + 1, k, t), F(i, j, k  1, t), F(i, j, k, t  1), S} where S is sum of the submatrix having two opposite vertices respectively (i, j) and (k, t).
 This solution has the complexity of O((m x n)^2).
TESTER’S SOLUTION
Can be found here.