For square matrix , link suggested by Amit would work. Finding a sub- rectangle is tougher.
I would go this way; First scan from bottom right till top left and for every Non-zero member in matrix create this pair ( width , depth ). Width is how many continuous 1's ( including itself ) are there to its right, Depth is how many continuous 1's ( including itself ) are there down wards now select a point P(i,j) , which has value Pair ( W , D ) it means W-1 columns to right and D-1 rows below are '1' , Note: it doesn't give any info about diagonal entries to P , and we will see , we actually don't need them. Now think about all possible rectangles which could be made when P is left top corner so go columnwise from i to i + 1 , i +2 , i + (W-1) points ( call it P' point ) , at every step, see the minimum depth for all points between P and P' and keep calculating area by width X minDepth e.g. P has width = 3, depth = 4 and co-ordinates (i,j ) then go like this Area for A[i,j] and P'[i, j+1 ] = 2 X MinDepth( P, P') //A1 Area for A[i,j] and P"[i, j+2 ] = 3 X MinDepth( P, P', P") //A2 : Note MinDepth is Minimum Depth of all three points so far Take Max of A1,A2 and you would have max rectangle which could be created by having P as top left corner. Now , keep traveling P throughout this Matrix. There are few optimisation. A point with width W and depth D can AT MAX has a rectangle with AREA MAX = W * D so next time consider points only whose W * D > Max Area calcuated so far.E.g if you have already got a point which has sub rectangle with area = 12 no need to look for points which has such (W,D) pairs = ( 2,3) , (4,2) , (3,3) etc . Time complextiy : First time reverse traversal O(m * n ) /// m Rows , n Columns Second time , MAX AREA calculation for each points , worse case o(n) as we need to travel only column wise as explained above Above action to be done for m*n points so total O( mn * n ) = O(mn^2) So total Time = O ( m * n^2 ) Time complexity :O ( 2 * m * n ) as W and D pair for each entry has to be maintained Suggestions, Clarifications, Modifications ? -Manish -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.