The Bannerwright and the Old Wall
The bannerwright has one rectangular cloth to hang flat against the old town wall, and wants it as large as she can make it.
The wall is a row of upright stone columns standing side by side on level ground, each exactly one unit wide. stones is a list of integers giving the column heights in order from west to east; every height is 0 or greater, and a height of 0 is a gap where no stone stands.
A cloth hangs across some run of consecutive columns and rests on the ground. It must sit entirely against stone, so a cloth spanning columns i through j (inclusive) can be no taller than the shortest column in that run, and its area is (j - i + 1) multiplied by that shortest height.
Write widestBanner(stones), which returns the largest area of any single such cloth, as an integer. If stones is empty, return 0.
examples
- case 1
stones of [2, 1, 5, 6, 2, 3]10 - the two columns of heights 5 and 6 carry a cloth 2 wide and 5 tall - case 2
stones of [6, 5, 4, 3, 2, 1]12 - the first three columns at height 4, or the first four at height 3 - case 3
stones of [2, 3, 0, 4, 5, 1]8 - the gap splits the wall; the best cloth is 2 wide and 4 tall over the columns of heights 4 and 5 - case 4
stones of []0
- reward
- 360 XP
- signature
widestBanner
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- the six columns
- no wall at all
- a lone column
- the descending wall
- nothing but gaps
- the level wall
- the valley between towers
- a gap splits the wall
- the sawtooth wall