A choreographed water-fountain show lines up n jets in a single row, numbered 1 to n from left to right. Every jet i can spray a column of water to any positive integer height, but its nozzle pressure caps that height at capHeight[i] units.
For the grand finale, the director wants the row of spray heights to read as a single mountain when the audience looks down the line: there must exist some peak jet p such that heights are non-decreasing from jet 1 through jet p, and non-increasing from jet p through jet n. (The peak may be the very first jet, the very last jet, or anywhere in between — a row that only rises, or only falls, is still a valid mountain with its peak at one end.)
Subject to 1 <= height[i] <= capHeight[i] for every jet and the single-mountain shape described above, find the maximum possible total height — the sum of all n spray heights — the director can achieve.
Line 1: an integer n, the number of jets. Line 2: n space-separated integers capHeight[1], ..., capHeight[n], the nozzle height cap for each jet.
Print a single integer: the maximum total height achievable across all n jets under the mountain-shape rule.
Example 1
Input
5 5 3 4 1 1
Expected
13
Explanation
Placing the peak at jet 1 gives heights = [5, 3, 3, 1, 1]: every cap is respected (5<=5, 3<=3, 3<=4, 1<=1, 1<=1) and the row is non-increasing all the way from jet 1 to jet 5, so it is a valid mountain whose peak sits at the left end. Its total is 5+3+3+1+1 = 13, the maximum possible.
Example 2
Input
6 6 5 3 9 2 7
Expected
22
Explanation
Placing the peak at jet 4 (its own cap, 9) and filling outward with the largest values that keep the left side non-decreasing and the right side non-increasing without exceeding any cap gives heights = [3, 3, 3, 9, 2, 2]. Every cap is respected (3<=6, 3<=5, 3<=3, 9<=9, 2<=2, 2<=7) and the total is 3+3+3+9+2+2 = 22, 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 →