Hi, the problem is -
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 recursive 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?