# Beautiful Towers I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/beautiful-towers-i)
Canonical: https://scaleengineer.com/dsa/problems/beautiful-towers-i
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [Salesforce](https://scaleengineer.com/companies/salesforce)
---
## Problem
You are given an array `heights` of `n` integers representing the number of bricks in `n` consecutive towers. Your task is to remove some bricks to form a **mountain-shaped** tower arrangement. In this arrangement, the tower heights are non-decreasing, reaching a maximum peak value with one or multiple consecutive towers and then non-increasing.

Return the **maximum possible sum** of heights of a mountain-shaped tower arrangement.

**Example 1:**

**Input:** heights = \[5,3,4,1,1\]

**Output:** 13

**Explanation:**

We remove some bricks to make `heights = [5,3,3,1,1]`, the peak is at index 0.

**Example 2:**

**Input:** heights = \[6,5,3,9,2,7\]

**Output:** 22

**Explanation:**

We remove some bricks to make `heights = [3,3,3,9,2,2]`, the peak is at index 3.

**Example 3:**

**Input:** heights = \[3,2,5,5,2,3\]

**Output:** 18

**Explanation:**

We remove some bricks to make `heights = [2,2,5,5,2,2]`, the peak is at index 2 or 3.

**Constraints:**

* `1 <= n == heights.length <= 103`
* `1 <= heights[i] <= 109`

# Approaches
## Brute Force by Iterating Through All Peaks
A straightforward approach is to consider every possible tower as the peak of the mountain. For each potential peak, we can calculate the total number of bricks in the resulting mountain-shaped arrangement and keep track of the maximum sum found. This method exhaustively checks every valid mountain configuration that can be formed.
**Time:** O(N^2), where N is the number of towers. The outer loop runs N times, and for each iteration, we perform two inner loops that together iterate through the rest of the array, taking O(N) time. · **Space:** O(1), as we only use a few variables to store the current sum and last height, not counting the input storage.
**Pros:** Simple to understand and implement.; Requires minimal extra space.
**Cons:** Inefficient for large inputs due to its quadratic time complexity. It might result in a 'Time Limit Exceeded' error on platforms with stricter time limits or larger constraints.
### Explanation
We iterate through each index `i` from `0` to `n-1`, treating `heights[i]` as the peak of the mountain. For each `i`, we calculate the sum of heights for the corresponding mountain configuration. The height of the peak tower is `heights[i]`. To form the non-decreasing left side (from index `0` to `i-1`), we iterate backwards from `i-1` to `0`. The height of tower `j` is limited by its original height `heights[j]` and the height of the tower to its right, `new_heights[j+1]`. So, `new_heights[j] = min(heights[j], new_heights[j+1])`. Similarly, for the non-increasing right side (from index `i+1` to `n-1`), we iterate forwards from `i+1` to `n-1`. The height of tower `j` is `new_heights[j] = min(heights[j], new_heights[j-1])`. We sum up the heights of all towers in this configuration. We keep a global maximum variable, updating it with the sum for each peak `i` if it's larger. After checking all possible peaks, the global maximum will be our answer.

```java
import java.util.List;
import java.lang.Math;

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

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

            // Calculate sum for the right side (non-increasing)
            lastHeight = heights.get(i);
            for (int j = i + 1; j < n; j++) {
                lastHeight = Math.min(heights.get(j), lastHeight);
                currentSum += lastHeight;
            }

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

        return maxTotalSum;
    }
}
```
### Algorithm
- Initialize a variable `maxSum` to 0.
- Iterate through each index `i` from `0` to `n-1`, considering `i` as the peak of the mountain.
- For each potential peak `i`:
    - Initialize `currentSum` with the height of the peak, `heights.get(i)`.
    - Initialize a `lastHeight` variable to `heights.get(i)`.
    - **Calculate the sum for the left side (non-decreasing part):**
        - Iterate from `j = i-1` down to `0`.
        - The height at `j` is constrained by its original height and the height of the tower to its right. Update `lastHeight = min(heights.get(j), lastHeight)`.
        - Add this `lastHeight` to `currentSum`.
    - **Calculate the sum for the right side (non-increasing part):**
        - Reset `lastHeight` to `heights.get(i)`.
        - Iterate from `j = i+1` up to `n-1`.
        - The height at `j` is constrained by its original height and the height of the tower to its left. Update `lastHeight = min(heights.get(j), lastHeight)`.
        - Add this `lastHeight` to `currentSum`.
    - Update `maxSum = max(maxSum, currentSum)`.
- After checking all possible peaks, return `maxSum`.

## Dynamic Programming with Monotonic Stack
The brute-force approach recomputes the sums for the left and right sides of each potential peak repeatedly. We can optimize this by pre-calculating these sums. We can define `prefixSum[i]` as the maximum sum of a valid non-decreasing arrangement ending at index `i`, and `suffixSum[i]` as the maximum sum of a valid non-increasing arrangement starting at index `i`. The total sum for a mountain with a peak at `i` is then `prefixSum[i] + suffixSum[i] - heights.get(i)`. These prefix and suffix sums can be calculated efficiently in linear time using a monotonic stack.
**Time:** O(N). We perform three passes over the array (one for prefix sums, one for suffix sums, and one to combine them). Each pass takes O(N) time because each element is pushed onto and popped from the stack at most once. · **Space:** O(N). We use two arrays, `prefixSum` and `suffixSum`, of size N, and a stack that can grow up to size N in the worst case.
**Pros:** Highly efficient with linear time complexity, making it suitable for large inputs.; Optimal solution for this problem.
**Cons:** More complex to understand and implement compared to the brute-force approach.; Requires O(N) extra space for the auxiliary arrays and the stack.
### Explanation
The core idea is to break down the problem. For any peak `i`, the total sum is the sum of the left part (non-decreasing up to `i`) and the right part (non-increasing from `i`), with the peak's height `heights[i]` counted once.

We create two arrays, `prefixSum` and `suffixSum`.

**To calculate `prefixSum`:**
We iterate from left to right (`i = 0 to n-1`). We use a monotonic stack to efficiently find the previous element `p` that is smaller than or equal to the current element `heights[i]`. The sum for the prefix ending at `i` can be calculated based on the sum of the prefix ending at `p`. The towers between `p` and `i` will all have height `heights[i]`. The recurrence is `prefixSum[i] = prefixSum[p] + (i - p) * heights[i]`. If no such `p` exists, all towers from `0` to `i` take the height `heights[i]`, so `prefixSum[i] = (i + 1) * heights[i]`.

**To calculate `suffixSum`:**
This is symmetric to the `prefixSum` calculation. We iterate from right to left (`i = n-1 to 0`) and use a monotonic stack to find the next element `p` that is smaller than or equal to `heights[i]`. The recurrence is `suffixSum[i] = suffixSum[p] + (p - i) * heights[i]`. If no such `p` exists, `suffixSum[i] = (n - i) * heights[i]`.

**Final Calculation:**
After computing both arrays, we iterate from `i = 0 to n-1` and find the maximum value of `prefixSum[i] + suffixSum[i] - heights.get(i)`. The `heights.get(i)` is subtracted because it's counted in both `prefixSum[i]` and `suffixSum[i]`.

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

class Solution {
    public long maximumSumOfHeights(List<Integer> heights) {
        int n = heights.size();
        long[] prefixSum = new long[n];
        Stack<Integer> stack = new Stack<>();

        // Calculate prefix sums
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights.get(stack.peek()) > heights.get(i)) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                prefixSum[i] = (long)(i + 1) * heights.get(i);
            } else {
                int p = stack.peek();
                prefixSum[i] = prefixSum[p] + (long)(i - p) * heights.get(i);
            }
            stack.push(i);
        }

        long[] suffixSum = new long[n];
        stack.clear();

        // Calculate suffix sums
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights.get(stack.peek()) > heights.get(i)) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                suffixSum[i] = (long)(n - i) * heights.get(i);
            } else {
                int p = stack.peek();
                suffixSum[i] = suffixSum[p] + (long)(p - i) * heights.get(i);
            }
            stack.push(i);
        }

        long maxTotalSum = 0;
        for (int i = 0; i < n; i++) {
            maxTotalSum = Math.max(maxTotalSum, prefixSum[i] + suffixSum[i] - heights.get(i));
        }

        return maxTotalSum;
    }
}
```
### Algorithm
- Create two long arrays, `prefixSum` and `suffixSum`, of size `n`.
- **Calculate `prefixSum`:**
    - Initialize an empty stack to store indices.
    - Loop `i` from `0` to `n-1`:
        - While the stack is not empty and `heights[stack.peek()] > heights[i]`, pop from the stack.
        - If the stack is empty, it means all previous elements are taller. The sum is `prefixSum[i] = (long)(i + 1) * heights[i]`.
        - Otherwise, let `p = stack.peek()`. The sum is `prefixSum[i] = prefixSum[p] + (long)(i - p) * heights[i]`.
        - Push `i` onto the stack.
- **Calculate `suffixSum`:**
    - Clear the stack.
    - Loop `i` from `n-1` down to `0`:
        - While the stack is not empty and `heights[stack.peek()] > heights[i]`, pop from the stack.
        - If the stack is empty, `suffixSum[i] = (long)(n - i) * heights[i]`.
        - Otherwise, let `p = stack.peek()`. The sum is `suffixSum[i] = suffixSum[p] + (long)(p - i) * heights[i]`.
        - Push `i` onto the stack.
- **Combine Results:**
    - Initialize `maxSum = 0`.
    - Loop `i` from `0` to `n-1`:
        - Calculate the total sum for a peak at `i` as `prefixSum[i] + suffixSum[i] - heights[i]`.
        - Update `maxSum` with the maximum sum found.
- Return `maxSum`.

# Solutions
### Java

```java
class Solution {
public
  long maximumSumOfHeights(List<Integer> maxHeights) {
    long ans = 0;
    int n = maxHeights.size();
    for (int i = 0; i < n; ++i) {
      int y = maxHeights.get(i);
      long t = y;
      for (int j = i - 1; j >= 0; --j) {
        y = Math.min(y, maxHeights.get(j));
        t += y;
      }
      y = maxHeights.get(i);
      for (int j = i + 1; j < n; ++j) {
        y = Math.min(y, maxHeights.get(j));
        t += y;
      }
      ans = Math.max(ans, t);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maximumSumOfHeights(vector<int> &maxHeights) {
    long long ans = 0;
    int n = maxHeights.size();
    for (int i = 0; i < n; ++i) {
      long long t = maxHeights[i];
      int y = t;
      for (int j = i - 1; ~j; --j) {
        y = min(y, maxHeights[j]);
        t += y;
      }
      y = maxHeights[i];
      for (int j = i + 1; j < n; ++j) {
        y = min(y, maxHeights[j]);
        t += y;
      }
      ans = max(ans, t);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int: ans, n = 0, len(maxHeights) for i, x in enumerate(maxHeights): y = t = x for j in range(i - 1, - 1, - 1): y = min(y, maxHeights[j]) t += y y = x for j in range(i + 1, n): y = min(y, maxHeights[j]) t += y ans = max(ans, t) return ans

```