# 2865. Beautiful Towers I

## Problem Statement

<br>

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*.

&#x20;

**Example 1:**

<pre><code><strong>Input: maxHeights = [5,3,4,1,1]
</strong><strong>Output: 13
</strong><strong>Explanation: One beautiful configuration with a maximum sum is heights = [5,3,3,1,1]. This configuration is beautiful since:
</strong>- 1 &#x3C;= heights[i] &#x3C;= 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.
</code></pre>

**Example 2:**

<pre><code><strong>Input: maxHeights = [6,5,3,9,2,7]
</strong><strong>Output: 22
</strong><strong>Explanation: One beautiful configuration with a maximum sum is heights = [3,3,3,9,2,2]. This configuration is beautiful since:
</strong>- 1 &#x3C;= heights[i] &#x3C;= 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.
</code></pre>

**Example 3:**

<pre><code><strong>Input: maxHeights = [3,2,5,5,2,3]
</strong><strong>Output: 18
</strong><strong>Explanation: One beautiful configuration with a maximum sum is heights = [2,2,5,5,2,2]. This configuration is beautiful since:
</strong>- 1 &#x3C;= heights[i] &#x3C;= 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.
</code></pre>

&#x20;

**Constraints:**

* `1 <= n == maxHeights <= 103`
* `1 <= maxHeights[i] <= 109`

## Intuition

```
Approach:

Consider each element as peak , and try to find the answer
```

### Links

<https://leetcode.com/problems/beautiful-towers-i/description/>

### Video Links

### Approach 1:

```
Brute Force 
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    long long maximumSumOfHeights(vector<int>& arr) {
        long long ans = 0;
        for(int i=0; i<arr.size(); i++){
            int idx = i;
            int peak = arr[idx];
            vector<int> arr_temp(arr);
            for(int i=idx-1; i>=0; i--){
                if(arr_temp[i] == peak)
                    continue;
                else if(arr_temp[i] < peak)
                    peak = arr_temp[i];
                else
                    arr_temp[i] = peak;
            }
            peak = arr_temp[idx];
            for(int i=idx+1; i<arr_temp.size(); i++){
                if(arr_temp[i] == peak)
                    continue;
                else if(arr_temp[i] < peak)
                    peak = arr_temp[i];
                else
                    arr_temp[i] = peak;
            }
            long long temp=0;
            for(auto &j: arr_temp)
                temp += j;

            ans = max(ans, temp);
        }

        return ans;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###