A marching band's halftime show places n riser podiums in a single row across the field, numbered 1 to n from one sideline to the other. Structural engineers have certified podium i to safely hold a performer stand of any positive integer height up to podiumCap[i].
The show's designer wants the row of podium heights to trace a single smooth rise-and-fall silhouette visible from the stands: there must exist some lead podium p such that heights are non-decreasing from podium 1 through podium p, and non-increasing from podium p through podium n. (p may be the first podium, the last podium, or anywhere in between.)
Subject to 1 <= height[i] <= podiumCap[i] for every podium and the single rise-and-fall shape described above, find the maximum possible total height — the sum of all n podium heights — the designer can achieve. A field show can seat up to 100000 podiums, so your solution must scale well beyond a simple quadratic scan over every possible lead podium.
Line 1: an integer n, the number of podiums. Line 2: n space-separated integers podiumCap[1], ..., podiumCap[n], the certified height cap for each podium.
Print a single integer: the maximum total height achievable across all n podiums under the rise-and-fall rule.
Example 1
Input
5 4 2 6 3 1
Expected
14
Explanation
Placing the lead podium at podium 3 (its own cap, 6) and filling outward gives heights = [2, 2, 6, 3, 1]: podiums 1-2 rise to 2 then 2 (each held below the cap of 6), and podiums 4-5 fall to 3 then 1. Every cap is respected and the total is 2+2+6+3+1 = 14, the maximum possible.
Example 2
Input
6 1 5 1 5 1 5
Expected
10
Explanation
Placing the lead podium at podium 2 (its own cap, 5) gives heights = [1, 5, 1, 1, 1, 1]: podium 1 is capped at 1, and podiums 3-6 must stay non-increasing from 5, but their own caps (1, 5, 1, 5) force them all down to 1 regardless. The total is 1+5+1+1+1+1 = 10, the maximum possible.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →