861. The Tallest Mountain Under the Caps
A row of n towers is to be built. Tower i may be any height h[i] with
1 <= h[i] <= cap[i], and the finished row must be a MOUNTAIN: there is a peak position p such
that the heights do not decrease up to p and do not increase after it.
Print the largest possible total height.
5 3 4 -> 11
6 5 3 9 2 7 -> 22
4 4 4 4 -> 16
For the first row, the peak must be at position 1 or 3; 5 3 3 totals 11 and 3 3 4 totals 10,
so 11 wins. Note that the cap 5 is used in full while the cap 4 is not.
## Fixing the peak makes the rest greedy
Suppose the peak is at p. Then h[p] = cap[p], and going left the heights must not increase, so
the best is
h[i] = min( cap[i], h[i+1] )
which is a running minimum of the caps from p leftwards. The right side is the mirror image. So
best(p) = leftBest(p) + rightBest(p) - cap[p]
where leftBest(p) is the total of the running minimum from p down to 0, rightBest(p) is the
same going right, and cap[p] is subtracted because the peak is in both.
Computing each best(p) directly is O(n), so trying all peaks is O(n^2). At n = 100000
that is 10^10.
## The stack recurrence for leftBest
leftBest obeys a recurrence driven by the nearest smaller cap on the left. Let j be the
nearest index below i with cap[j] < cap[i]. Then, in the running minimum starting at i,
every position from j+1 to i takes the value cap[i] (nothing between them is smaller), and
from j leftwards the profile is exactly the one leftBest(j) already describes:
leftBest(i) = leftBest(j) + cap[i] * (i - j) when j exists
leftBest(i) = cap[i] * (i + 1) when it does not
A monotonic stack that pops while cap[top] >= cap[i] finds j in amortised constant time, and
the whole array is computed in one pass. rightBest is the same pass run backwards.
Two stacks, two arrays, one final maximum. That is the entire solution.
## Why the popped ones never come back
When cap[i] is at most cap[top], the top can never again be the nearest strictly smaller cap
for anything to the right, because i is no larger and strictly nearer. Dominated on both counts,
so it is discarded permanently, and the pass is O(n).
## The ties, and what they cost
Pop on cap[top] >= cap[i], so the boundary j is strictly smaller. Equal caps are then absorbed
into the current block, which is correct: the running minimum does not drop at an equal cap. With a
strict pop the equal caps stay on the stack and leftBest is built from too many small blocks,
which undercounts. The row 4 4 4 4 must answer 16 and is exactly this test.
## Size
The total is up to n * max(cap), which is 10^14. 64 bits everywhere, including the
intermediate cap[i] * (i - j).
## Related problems
Problem 856 uses the same "previous boundary plus a closed-form block" recurrence with an arithmetic series instead of a rectangle. Problem 838 computes the same boundaries for a width rather than a sum.
## Cost
Time O(n), two stack passes. Space O(n).
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ cap[i] ≤ 10^9` - the answer can reach `10^14`, so it needs 64 bits
Input
The first line contains one integer n.
The second line contains n integers cap[0] ... cap[n-1], the maximum height of each tower.
Output
Print one integer alone on a line: the largest total height of a mountain-shaped row that respects every cap. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.