Finding maximum rectangular frame in array of zeros and ones I've recently come across a following problem. In a rectangular array of ones and zeros one has to find maximum non-degenerate rectangle whose sides are filled with ones. By "maximum" i mean any rectangle with maximum possible perimeter. By "non-degenerate" i mean that all sides consist of at least two cells. We do not care about the points inside the rectangle. The only requirement is that its sides consist of cells filled with ones.

I know how to solve a similar problem where one needs to find maximum rectangle totally filled with ones (i.e. not only its border, but its interior too). But with this problem i got stuck so any ideas will be highly appreciated. I believe that there is some smart $O(max(m,n)^3)$ solution but can't see it yet.

Thanks in advance.

P.S.
This is not a problem from an ongoing competition, hometask problem or an interview question. The problem originates from KPI-OPEN 2017 competition. You can find original statement here (problem F): http://kpi-open.kpi.ua/problemset/kpi_open_2017_2/eng.pdf

According to bounds on rectangle's size and time limitations there has to be at most cubic (or perhaps cubic-logarithmic) solution. As far as i know there were cubic solutions during the contest.

P.P.S.
There is an algorithm which precomputes for each cell how many cells there are to the left and above it which are filled with ones. Using such precomputation we can easily solve the problem in $O(max(m,n)^4)$ considering all possible rectangles. We just iterate through all possible cells for upper left corner of rectangle and through all possible cells for lower right corner. With the precomputation we might check in $O(1)$ that our rectangle is appropriate and if it is we just update the answer. Unfortunately such approach is to slow.
Yes, it is solvable in $O(\max(m,n)^3)$ time.  In fact, it should be solvable in $O(\min(m,n)^2 \max(m,n))$ time -- e.g., if $m&lt;n$, it should be solvable in $O(m^2 n)$ time.

Let $N_\text{down}(i,j)$ denote the number of cells that you can go down, starting from $(i,j)$, without encountering a zero.  Similarly, let $N_\text{right}(i,j)$ denote the number you can go right.  You can precompute all of these values in $O(mn)$ time.  Do you see how?

Now, I'm going to give you some hints, to help you solve this on your own.  Hint #1:


   Suppose I told you that the left side of the rectangle is at column $j_0$ and the right side is at column $j_1$.  Could you find the top and bottom sides of the rectangle with maximum perimeter?  How efficiently could you find it?


Hint #2:


   Continuing from Hint #1 -- can you identify some necessary and sufficient conditions to recognize the upper-left corner of the rectangle, $(i_0,j_0)$?  What would have to be true about the $N_\text{down}$ and $N_\text{right}$ values?  Similarly for the lower-left corner.


Hint #3:


   Try a linear scan downwards in those two columns.  In fact, all you need are the $N_\text{right}$ values.