Loading...
Loading...
Loading...
For the college fest, the decoration team wants to paint one large rectangular banner on a row of n hostel blocks. The blocks stand side by side, each one 1 metre wide, and block i is h[i] metres tall.
The banner must start at ground level, cover whole blocks next to each other, and stay on the walls: it cannot be taller than the shortest block it covers. Print the largest possible area of the banner in square metres.
Example 1
Input
7 6 2 5 4 5 1 6
Output
12
Blocks 3 to 5 (heights 5, 4, 5) give a banner 4 metres tall and 3 metres wide, so the area is 12.
Example 2
Input
3 2 1 2
Output
3
A banner 1 metre tall over all three blocks has area 3, more than either block of height 2 alone.
Try the problem first. Open one hint at a time.
In the best banner, some block is the shortest one it covers. Try every block as that shortest block.
For a block, the banner can stretch left and right until it meets a lower block. You need the nearest lower block on each side.
Keep a stack of block numbers whose heights go up from bottom to top. When a lower block arrives, pop the taller ones: for each popped block, the new block is its right limit and the block under it in the stack is its left limit.
Add a block of height 0 after the last one, so every block left on the stack gets popped. Areas reach 10^14, so use long.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor