Finding maximum rectangular frame in array of zeros and ones
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.