Maximize Total Height in a Mountain of Towers
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Maximize Total Height in a Mountain of Towers
You are given a 0-indexed array `maxHeights` of `n` integers. Choose an integer height `heights[i]` for the tower at coordinate `i`.
A valid configuration must satisfy `1 <= heights[i] <= maxHeights[i]` at every position and form a mountain: there must be an index `p` such that the heights are nondecreasing through `p` and nonincreasing after `p`. Formally:
- For every `0 < j <= p`, `heights[j - 1] <= heights[j]`.
- For every `p <= k < n - 1`, `heights[k + 1] <= heights[k]`.
Return the maximum possible sum of all chosen heights. Equal neighboring heights are allowed, and a peak may be at either endpoint.
### Examples
**Example 1**
```text
Input: maxHeights = [4,1,3,3]
Output: 8
```
The heights `[1,1,3,3]` form a valid mountain with sum `8`. Considering peak indices `0`, `1`, `2`, and `3`, the largest achievable sums are respectively `7`, `4`, `8`, and `8`.
**Example 2**
```text
Input: maxHeights = [2,4,1,5,3]
Output: 11
```
The configuration `[1,1,1,5,3]` has sum `11`. The largest sums for peaks `0` through `4` are `7`, `9`, `5`, `11`, and `9`, so no peak gives a larger total.
### Constraints
- `1 <= n == maxHeights.length <= 10^5`.
- `1 <= maxHeights[i] <= 10^9`.
### Clarifying Questions
- Must both sides of the mountain be nonempty? No; a peak at `0` or `n - 1` is valid.
- Must heights increase or decrease strictly? No; plateaus are allowed.
- Do we return the configuration itself? No; return only its maximum total height.
- Can a chosen height be zero or exceed its corresponding bound? No; every chosen height must remain in `[1, maxHeights[i]]`.
### C++ Interface
```cpp
class Solution {
public:
long long maximumSumOfHeights(vector<int>& maxHeights) {
}
};
```
### Reasoning Checkpoints
- Account for every possible location of a peak, including endpoints and plateaus.
- Explain why the selected heights obey both the individual bounds and the mountain condition.
- Handle the largest array length and total height without overflow.
```hint Reuse work between candidate peaks
For one chosen peak, the largest feasible height at a position is the minimum bound between that position and the peak. Can a monotonic stack help compute the sums of these interval minima for every peak?
```
Overview: Choose bounded positive tower heights that form a mountain, allowing plateaus and endpoint peaks, and return the greatest possible total height.