Answer for question 1: http://geeksforgeeks.org/?p=6257
And, I think the same solution can be extended/manipulated for rectangular matrix with largest number of 1's. Regards, Amit On Wed, Apr 28, 2010 at 10:23 PM, Vivek S <[email protected]> wrote: > Let Memo[i][j] be the sum of elements in the (sub) rectangle from (0,0) to > (i,j) > > Then use principle of inclusion and exclusion to find the sum of elements > from (a, b) to (c, d) in O(1) > > for N*N matrix, Complexity is O(N^4) > > On 28 April 2010 13:36, Ashish Mishra <[email protected]> wrote: > >> you are given a M x N matrix with 0's and 1's >> find the matrix with largest number of 1, >> 1. find the largest square matrix with 1's >> 2. Find the largest rectangular matrix with 1's >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > "Reduce, Reuse and Recycle" > Regards, > Vivek.S > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
