We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
consider h[i] = 1 for i=0..5, = 3 for i=6..8, =2 for i=9..11, =1 for i=12.
Then your divide & conquer solution should find 3(width)x3(height) for the left part, 3(width)x2(height) for the right part, end even if it glues together these two and finds that this can give a 6(width)x2(height) = 12 rectangle, how can it take into account the 9x1 rectangle left + 4x1 rectangle right which give 13 ? Unless your sub-problem solver returns a whole list of rectangles for the left and for the right part and then checks how they can be glued together... Then actually you do in a more complicated way the same what can be done with a stack in a single linear run.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Largest Rectangle
You are viewing a single comment's thread. Return to all comments →
consider h[i] = 1 for i=0..5, = 3 for i=6..8, =2 for i=9..11, =1 for i=12.
Then your divide & conquer solution should find 3(width)x3(height) for the left part, 3(width)x2(height) for the right part, end even if it glues together these two and finds that this can give a 6(width)x2(height) = 12 rectangle, how can it take into account the 9x1 rectangle left + 4x1 rectangle right which give 13 ? Unless your sub-problem solver returns a whole list of rectangles for the left and for the right part and then checks how they can be glued together... Then actually you do in a more complicated way the same what can be done with a stack in a single linear run.