Answer Happy

Bonus Question (10 points): You are designing the shape of a new room in some building. You have been given n columns, each of the same unit thickness, but with different heights: A[1], A[2], ..., A[n]. You can permute the columns in a line to define the shape of the room. To make matters difficult, you need to hang a large rectangular picture on the columns. If j consecutive columns in your order all have a height of at least k, then we can hang a rectangle of size j x k. i12345678 AU64502712 The example in the picture contains 3 consecutive columns with heights of at least 4, so we can hang a rectangle of area 12 on the first three columns a) Give an efficient algorithm to find the largest area of a hangable rectangle for the initial order A[1], A[2], ..., A[n] of columns. b) Devise an efficient algorithm to permute the columns into an order that maximizes the area of a hangable rectangle.