Maximum Total Height of Mountain-Shaped Towers Under Per-Plot Height Caps
Company: Virtu
Role: Quantitative Researcher
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Online Assessment
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
```python
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**
```text
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**
```text
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**
```text
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`.
Overview: Each plot in a row has a maximum allowed tower height. Choose tower heights that rise to a single peak and then fall, never exceeding any cap, so that the total height is as large as possible. Tests reasoning about the peak position, per-position caps, and 64-bit sums.
Read the full Virtu Quantitative Researcher interview experience this question came from
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.
Formally, `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 also a mountain.
Implement `max_mountain_sum(max_heights)` and return the maximum possible total height of all `n` towers. Return only this maximum total (a single integer), not the heights themselves.
The answer can be as large as `10^12`, which exceeds `2^31 - 1`, so use 64-bit integers (`long` in Java, `long long` in C++). It stays far below `2^53`, so it is exact as a JavaScript number.
### 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`; it stays far below `2^53`.
### Example 1
```text
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
```text
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`.
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 (long in Java, long long in C++). It stays far below 2^53.
Examples
Input: ([5, 3, 4, 1, 1],)
Expected Output: 13
Explanation: Source example 1: heights [5, 3, 3, 1, 1] with the peak at plot 0.
Input: ([6, 5, 3, 9, 2, 7],)
Expected Output: 22
Explanation: Source example 2: heights [3, 3, 3, 9, 2, 2] with the peak at plot 3; the right side is clipped to 2.
Hints
- 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?
- Walking outward from the peak, a tower can never be taller than any cap between it and the peak, including its own.
- Totals can reach 10^12, which is beyond 32-bit range, so keep running sums in 64-bit integers.