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 <amishra....@gmail.com> 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 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.
