PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
This problem can be solved by combining brute-force and dynamic programming (DP):
-
At first, we find all non-empty sub-matrices, 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 O-region. To do it, we must find the non-empty sub-matrix 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 sub-matrix 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 sub-matrix 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.