Kadane's Algorithm.
Before we get into bigger matrices, let's just consider $1\times n$ matrices - that is, integer sequences of length $n$. Determining the maximum submatrix in this context means finding the maximum contiguous subsequence, and for that we have Kadane's algorithm, which runs for the low low price of $O(n)$. It goes like this:
kadane($x_1,\ldots,x_n$):
$\hspace{10pt}$m \leftarrow -\infty$, $\hspace{10pt}$a \leftarrow 0$, $\hspace{10pt}b \leftarrow 0$,
$\hspace{10pt}c_m\leftarrow 0$, $\hspace{10pt}c_a\leftarrow 1$
$\hspace{10pt}$for $c_{\,b}=1$ to $n$ do
$\hspace{30pt}c_m \leftarrow c_m \!+\, x_b$
$\hspace{30pt}$if $c_m>m$ then
$\hspace{50pt}$m \leftarrow c_m$, $\hspace{10pt}$a\leftarrow c_a$, $\hspace{10pt}b\leftarrow c_{\,b}$
$\hspace{30pt}$if $c_m<0$ then
$\hspace{50pt}c_m \leftarrow 0$, $\hspace{10pt}$$c_a\leftarrow c_{\,b}+1$
$\hspace{10pt}$return $m,a,b$
So, given an integer sequence $x_1,\ldots, x_n$, kadane will return the maximum sum $m$ and the endpoints on the interval from which it is attained: $a$ to $b$.
Adapting this to your problem.
To solve your problem, you will first have to adapt Kadane's algorithm to the $m\times n$ case. This isn't too hard; it's just a "double Kadane," going in two directions, ultimately coming out at $O(n^3)$. Since I now see this problem is for a contest, I won't finish it explicitly for you. However, my thought/suggestion is to see if you can use the $2$-dimensional Kadane in conjunction with permutations of rows and columns, then figure out the most efficient way to track the action on the sum.