This problem was recently posted in a TopCoder match: http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm337
Checkout BuildingAdvertise problem in above editorial. On 3/12/07, Karthik Singaram L <[EMAIL PROTECTED]> wrote: > > 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. > > > > -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
