We have given binary matrix (matrix containing only 1 and 0) of size $n\cdot m$. We want to order the matrix such that the biggest rectangle containing only ones is with maximum size.
For example if the following matrix is given:
1000 0010
1101 0111
1101 0111
1101 0111
We should output 9 because the biggest rectangle we can get is with size 9. We are allowed to swap any columns infinite number of times and we are only requested to find the maximum size of the subrectangle.
Can we solve this problem faster that trying all possible permutations?