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.