n plots, and a building goes up on each one. Plot i has a height cap limits[i]: its building must be between 1 and limits[i] tall, inclusive.
The street's skyline must form a hill: heights never decrease up to some peak plot and never increase after it. The peak may be at either end of the street.
Return the largest possible total height of all the buildings.
There can be up to 10⁵ plots, so trying every peak and walking the whole street for each one is too slow.limits=[2, 7, 3, 9, 1] → 18
Put the peak on plot 3 (height 9): the heights to its left are [2, 3, 3] and 1 follows on the right. The row [2, 3, 3, 9, 1] sums to 18. A peak on plot 1 would give [2, 7, 3, 3, 1], only 16.
limits=[5, 4, 4, 1] → 14
The caps never increase already, so every building can reach its cap: 5 + 4 + 4 + 1 = 14.
limits=[6] → 6
limits[i] ≤ 10⁹limits=[2, 7, 3, 9, 1]
18
Run checks the first 3 tests in your browser. Submit checks all 113 tests on the server, hidden ones included.