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.