Maximum Total Height of Mountain-Shaped Towers Under Per-Plot Height Caps

You are planning n towers on plots 0 to n - 1 along a street. Each plot has a height cap: tower i must have an integer height heights[i] with 1 <= heights[i] <= max_heights[i]. The skyline must be a mountain: heights never decrease from the left end up to some peak plot, and never increase from that peak to the right end.

Return the maximum possible total height of all n towers.

Function Signature

def max_mountain_sum(max_heights: list[int]) -> int:

Rules

• heights is a mountain if there is an index p (the peak) such that heights[j - 1] <= heights[j] for every 1 <= j <= p, and heights[k] >= heights[k + 1] for every p <= k <= n - 2.
• Equal neighboring heights are allowed, and the peak may be the first or the last plot, so a non-increasing or non-decreasing sequence is a mountain.
• Return only the maximum total, not the heights.

Constraints

• 1 <= n <= 1000, where n = len(max_heights)
• 1 <= max_heights[i] <= 10^9
• The answer can be as large as 10^12, which exceeds 2^31 - 1, so use 64-bit integers. It stays far below 2^53.

Examples

Example 1

Input:  max_heights = [5, 3, 4, 1, 1]
Output: 13

One optimal choice is heights = [5, 3, 3, 1, 1], with the peak at plot 0.

Example 2

Input:  max_heights = [6, 5, 3, 9, 2, 7]
Output: 22

One optimal choice is heights = [3, 3, 3, 9, 2, 2], with the peak at plot 3.

Example 3

Input:  max_heights = [3, 2, 5, 5, 2, 3]
Output: 18

One optimal choice is heights = [2, 2, 5, 5, 2, 2], with the peak at plot 2 or 3.

Maximum Total Height of a Mountain Skyline Under Height Caps

Hints

1. Try fixing which plot is the peak first. Once the peak is fixed, does each remaining tower's best height still depend on the choices made for the other towers?
2. Walking outward from the peak, a tower can never be taller than any cap between it and the peak, including its own.
3. Totals can reach 10^12, which is beyond 32-bit range, so keep running sums in 64-bit integers.

Approach

Fix a peak p. Any mountain with peak p satisfies heights[k] <= heights[k+1] <= ... <= heights[p] for k < p (and symmetrically for k > p), and each of those heights is at most its own cap, so heights[k] <= min(max_heights[k..p]) (or min(max_heights[p..k]) on the right), and heights[p] <= max_heights[p]. Setting every tower to exactly that bound is itself a valid mountain within the caps (the bounds are non-decreasing toward p from both sides and each is >= 1), so it is the best mountain for peak p. The answer is therefore max over p of left[p] + right[p] - max_heights[p], where left[p] is the sum of the running minima from p back to 0 and right[p] the sum of the running minima from p to n - 1 (the peak is counted in both, hence the subtraction).

Compute left with a monotonic stack of indices whose caps are non-decreasing: at index i, pop every index whose cap is greater than max_heights[i]. The remaining top j (if any) is the nearest index to the left with cap <= max_heights[i], so every plot in (j, i] gets height max_heights[i], and for every plot at or before j the minimum toward i equals its minimum toward j, giving left[i] = left[j] + max_heights[i] * (i - j); with an empty stack, left[i] = max_heights[i] * (i + 1). right is the mirror image scanned from the right end. Each index is pushed and popped at most once per pass.

Edge cases: n = 1 returns the single cap; strictly increasing or decreasing caps put the peak at the last or first plot; equal adjacent maxima give the same total for either peak; the largest single cap is not necessarily the best peak when low caps around it clip the sides; totals reach 10^12, so every accumulator is 64-bit (long / long long).

• Time complexity: O(n)
• Space complexity: O(n)