# Beautiful Towers II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/beautiful-towers-ii)
Canonical: https://scaleengineer.com/dsa/problems/beautiful-towers-ii
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [Salesforce](https://scaleengineer.com/companies/salesforce)
---
## Problem
You are given a **0-indexed** array `maxHeights` of `n` integers.

You are tasked with building `n` towers in the coordinate line. The `ith` tower is built at coordinate `i` and has a height of `heights[i]`.

A configuration of towers is **beautiful** if the following conditions hold:

1. `1 <= heights[i] <= maxHeights[i]`
2. `heights` is a **mountain** array.

Array `heights` is a **mountain** if there exists an index `i` such that:

* For all `0 < j <= i`, `heights[j - 1] <= heights[j]`
* For all `i <= k < n - 1`, `heights[k + 1] <= heights[k]`

Return _the **maximum possible sum of heights** of a beautiful configuration of towers_.

**Example 1:**

**Input:** maxHeights = [5,3,4,1,1]
**Output:** 13
**Explanation:** One beautiful configuration with a maximum sum is heights = [5,3,3,1,1]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]  
- heights is a mountain of peak i = 0.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 13.

**Example 2:**

**Input:** maxHeights = [6,5,3,9,2,7]
**Output:** 22
**Explanation:** One beautiful configuration with a maximum sum is heights = [3,3,3,9,2,2]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]
- heights is a mountain of peak i = 3.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 22.

**Example 3:**

**Input:** maxHeights = [3,2,5,5,2,3]
**Output:** 18
**Explanation:** One beautiful configuration with a maximum sum is heights = [2,2,5,5,2,2]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]
- heights is a mountain of peak i = 2. 
Note that, for this configuration, i = 3 can also be considered a peak.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 18.

**Constraints:**

* `1 <= n == maxHeights.length <= 105`
* `1 <= maxHeights[i] <= 109`

# Approaches
## Brute Force by Iterating Through All Peaks
This approach directly translates the problem definition into a solution. We consider every possible index as the peak of the mountain. For each potential peak, we construct the optimal `heights` array and calculate its sum. The optimal construction for a fixed peak `i` involves setting `heights[i] = maxHeights[i]` and then greedily choosing the largest possible heights for the towers to the left and right while satisfying the mountain and `maxHeights` constraints. The final answer is the maximum sum found among all possible peak choices.
**Time:** O(N^2), where N is the number of towers. The outer loop runs N times for each potential peak, and the inner loops for calculating left and right sums take O(N) time in total for each peak. · **Space:** O(1) extra space, as we only use a few variables to store the current sums and heights during calculation.
**Pros:** Simple to understand and implement.; It correctly solves the problem for smaller input sizes.
**Cons:** This approach is too slow for the given constraints (`n` up to 10^5) and will likely result in a Time Limit Exceeded (TLE) error.
### Explanation
The core idea is to iterate through all possible indices `i` from `0` to `n-1` and assume each one is the peak of the mountain. When `i` is the peak, to maximize the total sum, we should set `heights[i]` to its maximum possible value, which is `maxHeights.get(i)`.

For the left side of the peak (`j < i`), the heights must be non-decreasing, i.e., `heights[j] <= heights[j+1]`. To maximize the sum, we set `heights[j]` to the largest value possible, which is `min(maxHeights.get(j), heights[j+1])`. We can calculate these heights and their sum by iterating from `i-1` down to `0`.

Similarly, for the right side of the peak (`k > i`), the heights must be non-increasing, i.e., `heights[k] <= heights[k-1]`. We set `heights[k] = min(maxHeights.get(k), heights[k-1])` and calculate the sum by iterating from `i+1` up to `n-1`.

The sum for a given peak `i` is the sum of all these calculated heights. We keep track of the maximum sum found across all iterations.

```java
import java.util.List;

class Solution {
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        int n = maxHeights.size();
        long maxTotalSum = 0;

        for (int i = 0; i < n; i++) {
            long currentSum = maxHeights.get(i);
            
            // Calculate sum for the left side (non-decreasing)
            long prevHeight = maxHeights.get(i);
            for (int j = i - 1; j >= 0; j--) {
                long currentHeight = Math.min(maxHeights.get(j), prevHeight);
                currentSum += currentHeight;
                prevHeight = currentHeight;
            }

            // Calculate sum for the right side (non-increasing)
            prevHeight = maxHeights.get(i);
            for (int k = i + 1; k < n; k++) {
                long currentHeight = Math.min(maxHeights.get(k), prevHeight);
                currentSum += currentHeight;
                prevHeight = currentHeight;
            }

            maxTotalSum = Math.max(maxTotalSum, currentSum);
        }

        return maxTotalSum;
    }
}
```
### Algorithm
- Initialize a variable `maxTotalSum` to 0.
- Iterate through each index `i` from `0` to `n-1`, considering it as the potential peak of the mountain array.
- For each `i`, calculate the sum of heights for a beautiful configuration with `i` as the peak.
  - Initialize `currentSum` with `maxHeights[i]`, as the peak tower will have its maximum possible height.
  - Initialize a variable `prevHeight` to `maxHeights[i]`.
  - Iterate backwards from `j = i - 1` to `0` to calculate the sum of the left side (non-decreasing part).
    - The height at `j` is `min(maxHeights[j], prevHeight)`.
    - Add this height to `currentSum` and update `prevHeight`.
  - Reset `prevHeight` to `maxHeights[i]`.
  - Iterate forwards from `k = i + 1` to `n-1` to calculate the sum of the right side (non-increasing part).
    - The height at `k` is `min(maxHeights[k], prevHeight)`.
    - Add this height to `currentSum` and update `prevHeight`.
- After calculating the `currentSum` for the peak `i`, update `maxTotalSum = max(maxTotalSum, currentSum)`.
- After iterating through all possible peaks, `maxTotalSum` will hold the result.

## Dynamic Programming with Monotonic Stack
The O(N^2) brute-force approach is slow because it repeatedly calculates sums for overlapping subarrays. We can optimize this by pre-calculating these sums. The key insight is that the total sum for a mountain with a peak at `i` can be decomposed into two independent subproblems: the maximum sum of a non-decreasing sequence ending at `i` and the maximum sum of a non-increasing sequence starting at `i`. These two sets of sums (for all `i`) can be computed efficiently in O(N) time using a monotonic stack. After pre-computation, we can find the maximum total sum in a final O(N) pass.
**Time:** O(N). Calculating `leftSum` takes O(N), `rightSum` takes O(N), and the final pass to combine them takes O(N). Each element is pushed and popped from the stack at most once. · **Space:** O(N), for storing the `leftSum` and `rightSum` arrays, and for the stack which can grow up to size N in the worst case.
**Pros:** Highly efficient with a linear time complexity.; Passes the given constraints with ease.
**Cons:** More complex to understand and implement correctly compared to the brute-force approach.; Requires knowledge of the monotonic stack data structure and its application.
### Explanation
This approach is based on dynamic programming and a monotonic stack. We pre-calculate two arrays:

1.  `leftSum[i]`: The maximum sum of a beautiful tower configuration for the prefix `maxHeights[0...i]` where the heights are non-decreasing (i.e., `i` is the peak of this prefix). We can compute this for all `i` in O(N) time. We iterate from left to right, maintaining a monotonic stack of indices where `maxHeights` values are increasing. For each `i`, we find the previous index `p` where `maxHeights[p] < maxHeights[i]`. All towers between `p` and `i` will have height `maxHeights[i]`. The total sum `leftSum[i]` can be derived from `leftSum[p]`. 

2.  `rightSum[i]`: Similarly, this is the maximum sum for the suffix `maxHeights[i...n-1]` where heights are non-increasing. This is calculated symmetrically by iterating from right to left.

Once both `leftSum` and `rightSum` arrays are populated, we can find the maximum possible sum for a mountain with a peak at index `i` by the formula: `leftSum[i] + rightSum[i] - maxHeights.get(i)`. We subtract `maxHeights.get(i)` because it was counted in both `leftSum[i]` and `rightSum[i]`. The final answer is the maximum value of this expression over all `i` from `0` to `n-1`.

```java
import java.util.List;
import java.util.Stack;

class Solution {
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        int n = maxHeights.size();
        
        long[] leftSum = new long[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            long currentMaxHeight = maxHeights.get(i);
            while (!stack.isEmpty() && maxHeights.get(stack.peek()) >= currentMaxHeight) {
                stack.pop();
            }
            
            if (stack.isEmpty()) {
                leftSum[i] = (long)(i + 1) * currentMaxHeight;
            } else {
                int prevSmallerIndex = stack.peek();
                leftSum[i] = leftSum[prevSmallerIndex] + (long)(i - prevSmallerIndex) * currentMaxHeight;
            }
            stack.push(i);
        }
        
        long[] rightSum = new long[n];
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            long currentMaxHeight = maxHeights.get(i);
            while (!stack.isEmpty() && maxHeights.get(stack.peek()) >= currentMaxHeight) {
                stack.pop();
            }
            
            if (stack.isEmpty()) {
                rightSum[i] = (long)(n - i) * currentMaxHeight;
            } else {
                int nextSmallerIndex = stack.peek();
                rightSum[i] = rightSum[nextSmallerIndex] + (long)(nextSmallerIndex - i) * currentMaxHeight;
            }
            stack.push(i);
        }
        
        long maxTotalSum = 0;
        for (int i = 0; i < n; i++) {
            maxTotalSum = Math.max(maxTotalSum, leftSum[i] + rightSum[i] - maxHeights.get(i));
        }
        
        return maxTotalSum;
    }
}
```
### Algorithm
- Define two arrays, `leftSum` and `rightSum`, of size `n` to store precomputed sums.
- **Calculate `leftSum`**: `leftSum[i]` will store the maximum sum of a valid non-decreasing sequence of towers on `maxHeights[0...i]` with `i` as the peak.
  - Use a monotonic stack (storing indices of `maxHeights` with increasing values) and iterate from `i = 0` to `n-1`.
  - For each `i`, pop from the stack while `maxHeights[stack.peek()] >= maxHeights[i]`.
  - The sum `leftSum[i]` can then be calculated in O(1) using the previously computed sum for the new stack top (`leftSum[p]`) and the value `maxHeights[i]`.
- **Calculate `rightSum`**: `rightSum[i]` will store the maximum sum of a valid non-increasing sequence of towers on `maxHeights[i...n-1]` with `i` as the peak.
  - This is symmetric to the `leftSum` calculation. Use a monotonic stack and iterate from `i = n-1` down to `0`.
- **Combine Results**: The maximum sum for a mountain with peak `i` is `leftSum[i] + rightSum[i] - maxHeights[i]` (subtracting `maxHeights[i]` because it's included in both sums).
- Iterate through all `i` from `0` to `n-1`, calculate this combined sum, and find the maximum value. This will be the final answer.

# Solutions
### Java

```java
class Solution {
public
  long maximumSumOfHeights(List<Integer> maxHeights) {
    int n = maxHeights.size();
    Deque<Integer> stk = new ArrayDeque<>();
    int[] left = new int[n];
    int[] right = new int[n];
    Arrays.fill(left, -1);
    Arrays.fill(right, n);
    for (int i = 0; i < n; ++i) {
      int x = maxHeights.get(i);
      while (!stk.isEmpty() && maxHeights.get(stk.peek()) > x) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        left[i] = stk.peek();
      }
      stk.push(i);
    }
    stk.clear();
    for (int i = n - 1; i >= 0; --i) {
      int x = maxHeights.get(i);
      while (!stk.isEmpty() && maxHeights.get(stk.peek()) >= x) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        right[i] = stk.peek();
      }
      stk.push(i);
    }
    long[] f = new long[n];
    long[] g = new long[n];
    for (int i = 0; i < n; ++i) {
      int x = maxHeights.get(i);
      if (i > 0 && x >= maxHeights.get(i - 1)) {
        f[i] = f[i - 1] + x;
      } else {
        int j = left[i];
        f[i] = 1L * x * (i - j) + (j >= 0 ? f[j] : 0);
      }
    }
    for (int i = n - 1; i >= 0; --i) {
      int x = maxHeights.get(i);
      if (i < n - 1 && x >= maxHeights.get(i + 1)) {
        g[i] = g[i + 1] + x;
      } else {
        int j = right[i];
        g[i] = 1L * x * (j - i) + (j < n ? g[j] : 0);
      }
    }
    long ans = 0;
    for (int i = 0; i < n; ++i) {
      ans = Math.max(ans, f[i] + g[i] - maxHeights.get(i));
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maximumSumOfHeights(vector<int> &maxHeights) {
    int n = maxHeights.size();
    stack<int> stk;
    vector<int> left(n, -1);
    vector<int> right(n, n);
    for (int i = 0; i < n; ++i) {
      int x = maxHeights[i];
      while (!stk.empty() && maxHeights[stk.top()] > x) {
        stk.pop();
      }
      if (!stk.empty()) {
        left[i] = stk.top();
      }
      stk.push(i);
    }
    stk = stack<int>();
    for (int i = n - 1; ~i; --i) {
      int x = maxHeights[i];
      while (!stk.empty() && maxHeights[stk.top()] >= x) {
        stk.pop();
      }
      if (!stk.empty()) {
        right[i] = stk.top();
      }
      stk.push(i);
    }
    long long f[n], g[n];
    for (int i = 0; i < n; ++i) {
      int x = maxHeights[i];
      if (i && x >= maxHeights[i - 1]) {
        f[i] = f[i - 1] + x;
      } else {
        int j = left[i];
        f[i] = 1LL * x * (i - j) + (j != -1 ? f[j] : 0);
      }
    }
    for (int i = n - 1; ~i; --i) {
      int x = maxHeights[i];
      if (i < n - 1 && x >= maxHeights[i + 1]) {
        g[i] = g[i + 1] + x;
      } else {
        int j = right[i];
        g[i] = 1LL * x * (j - i) + (j != n ? g[j] : 0);
      }
    }
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
      ans = max(ans, f[i] + g[i] - maxHeights[i]);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int: n = len(maxHeights) stk = [] left = [- 1] * n for i, x in enumerate(maxHeights): while stk and maxHeights[stk[- 1]] > x: stk . pop() if stk: left[i] = stk[- 1] stk . append(i) stk = [] right = [n] * n for i in range(n - 1, - 1, - 1): x = maxHeights[i] while stk and maxHeights[stk[- 1]] >= x: stk . pop() if stk: right[i] = stk[- 1] stk . append(i) f = [0] * n for i, x in enumerate(maxHeights): if i and x >= maxHeights[i - 1]: f[i] = f[i - 1] + x else: j = left[i] f[i] = x * (i - j) + (f[j] if j != - 1 else 0) g = [0] * n for i in range(n - 1, - 1, - 1): if i < n - 1 and maxHeights[i] >= maxHeights[i + 1]: g[i] = g[i + 1] + maxHeights[i] else: j = right[i] g[i] = maxHeights[i] * (j - i) + (g[j] if j != n else 0) return max(a + b - c for a, b, c in zip(f, g, maxHeights))

```