I give a try to start at an O(mn) algorithm (where m is the size of the longest bar)
Let Maxrect[i][j] denote the width of the maximum rectangle ending at the ith position of height j if(height[i] >= j) Maxrect[i][j] = Maxrect[i-1][j]+1 else Maxrect[i][j] = 0 We can traverse this array to find the maximum value in O(mn) now. This may not be the best but to just get things rolling. --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---