Contiguous All-one block in a matrix

Suppose you are given an mXn bitmap, represented by an array M[1..m,1.. n] whose entries are all 0 or 1. A all-one block is a subarray of the form M[i .. i0, j .. j0] in which every bit is equal to 1. Describe and analyze an efficient algorithm to find an all-one block in M with maximum area

I am trying to make a dynamic programming solution. But my rec开发者_JAVA百科ursive algorithm runs in O(n^n) time, and even after memoization I cannot think of bringing it down below O(n^4). Can someone help me find a more efficient solution?

This is only an idea, and I'm not sure is it working.

Define A(i,j)(di,dj) to be all-one block from (i,j) to (i+di,j+dj), that means M[x,y]=1 for i<=x<=i+di and j<=y<=j+dj.

Define A(i,j)(di,dj) as max-block if there doesn't hold A(i,j)(di+1,dj) and A(i,j)(di,dj+1).

For each (i,j) we can contruct list, call it L(i,j), of max-blocks. Max length of list is min(m-i+1, n-j+1) <= min(m,n).

L(i,j) depends only on M[i,j], L(i+1,j) and L(i,j+1). I think that constructing L(i,j) from L(i+1,j) and L(i,j+1) can be done in linear time, it reminds me on merging of sorted lists. With L(i,j), find max(di * dj) for A(i,j)(di,dj) in L(i,j). Maximal of these values specifies maximal all-one block.

This approach has complexity n*m*min(m,n) ~= n^3 and need min(m,n)^2 space for storing last 2 rows which are needed.