Given a $n \times m$ grid $G$, with each grid square having a value 0 or 1, find a rectangle $R$ in $G$ that maximizes $R_1 - R_0$, where $R_0,R_1$ are defined as follows:
$R_0$ = the total number of 0's in $R$
$R_1$ = the total number of 1's in $R$
The brute force solution is to compute the value $(R_1 - R_0)$ for all possible rectangles, then select the one with maximum value. There can be $1/4 \lbrace nm(n+1)(m+1) \rbrace$ possible rectangles in a $n \times m$ grid. [Source]
Is there a smarter way to do this? Can we relate this problem to the Maximal Rectangle Problem?
This problem turns out to be similar to this one. We just have to replace 0s with -1s, then find the rectangle with largest sum. Using the techniques shown there, the problem can be solved in $O(nm \cdot \min(n,m))$ time. Can we do better?