@Neha.. This problem can be solved by DP. Create an auxiliary matrix C[][] . C[i][j] would give the maximum size sub matrix with C[i][j] as the right bottom entry. now the DP eqn is
if M[i][j] == 1 C[i][j] = min(c[i-1][j],c[i][j-1],c[i-1][j-1])+1 else c[i][j] = 0 Now take the maximum c[i][j] entry in the matrix. Hope it helps. On Mon, Sep 12, 2011 at 10:07 AM, tech coder <techcoderonw...@gmail.com>wrote: > this is possible in o(n^2) with n^2 addidtional space . > > > On Sun, Sep 11, 2011 at 11:33 AM, Neha Singh > <neha.ndelhi.1...@gmail.com>wrote: > >> @victor: Can u provide the algo ?? >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@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. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. > -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
