Algorithms
Medium
2865
3114
Beautiful Towers I
beautiful-towers-i
"""
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 <= 103
 * 1 <= maxHeights[i] <= 109
"""
class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        
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 <= 103
 * 1 <= maxHeights[i] <= 109


Please complete the code below to solve above prblem:
```python
class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        
```

my_solution = Solution()

test_input = { "maxHeights": [5,3,4,1,1] }
assert my_solution.maximumSumOfHeights(**test_input) == 13

test_input = { "maxHeights": [6,5,3,9,2,7] }
assert my_solution.maximumSumOfHeights(**test_input) == 22

test_input = { "maxHeights": [3,2,5,5,2,3] }
assert my_solution.maximumSumOfHeights(**test_input) == 18

test_input = { "maxHeights": [1000000000] }
assert my_solution.maximumSumOfHeights(**test_input) == 1000000000

test_input = { "maxHeights": [1] }
assert my_solution.maximumSumOfHeights(**test_input) == 1

test_input = { "maxHeights": [933754743] }
assert my_solution.maximumSumOfHeights(**test_input) == 933754743

test_input = { "maxHeights": [1,1000000000] }
assert my_solution.maximumSumOfHeights(**test_input) == 1000000001

test_input = { "maxHeights": [1000000000,1000000000] }
assert my_solution.maximumSumOfHeights(**test_input) == 2000000000

test_input = { "maxHeights": [999999999,1000000000] }
assert my_solution.maximumSumOfHeights(**test_input) == 1999999999

test_input = { "maxHeights": [1000000000,999999999] }
assert my_solution.maximumSumOfHeights(**test_input) == 1999999999

test_input = { "maxHeights": [30,1] }
assert my_solution.maximumSumOfHeights(**test_input) == 31

test_input = { "maxHeights": [1,12,19] }
assert my_solution.maximumSumOfHeights(**test_input) == 32

test_input = { "maxHeights": [1000000000,1000000000,1000000000] }
assert my_solution.maximumSumOfHeights(**test_input) == 3000000000

test_input = { "maxHeights": [999999999,1000000000,999999999] }
assert my_solution.maximumSumOfHeights(**test_input) == 2999999998

test_input = { "maxHeights": [1000000000,999999999,999999998] }
assert my_solution.maximumSumOfHeights(**test_input) == 2999999997

test_input = { "maxHeights": [999999998,999999999,1000000000] }
assert my_solution.maximumSumOfHeights(**test_input) == 2999999997

test_input = { "maxHeights": [1,1,1] }
assert my_solution.maximumSumOfHeights(**test_input) == 3

test_input = { "maxHeights": [1,1,4,3,3,3,6] }
assert my_solution.maximumSumOfHeights(**test_input) == 20

test_input = { "maxHeights": [2,4,1,3,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 11

test_input = { "maxHeights": [1,5,2,5,6,4,6,3,4,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 33

test_input = { "maxHeights": [3,6,3,5,5,1,2,5,5,6] }
assert my_solution.maximumSumOfHeights(**test_input) == 24

test_input = { "maxHeights": [1,6,5,6,2,4,1,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 23

test_input = { "maxHeights": [5,1,6,5,4,4,2] }
assert my_solution.maximumSumOfHeights(**test_input) == 23

test_input = { "maxHeights": [3,4,3,1,1,3] }
assert my_solution.maximumSumOfHeights(**test_input) == 13

test_input = { "maxHeights": [4,1,6,5,3,6] }
assert my_solution.maximumSumOfHeights(**test_input) == 19

test_input = { "maxHeights": [3,5,5,6,4,6,5,6] }
assert my_solution.maximumSumOfHeights(**test_input) == 35

test_input = { "maxHeights": [6,4,3,3] }
assert my_solution.maximumSumOfHeights(**test_input) == 16

test_input = { "maxHeights": [6,4,3,6,1,2,2,3] }
assert my_solution.maximumSumOfHeights(**test_input) == 20

test_input = { "maxHeights": [6,5,1,4,6,1,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 16

test_input = { "maxHeights": [2,3,4,4,3,2,3,5,5,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 30

test_input = { "maxHeights": [5,4,6,1,2] }
assert my_solution.maximumSumOfHeights(**test_input) == 16

test_input = { "maxHeights": [1,4,2] }
assert my_solution.maximumSumOfHeights(**test_input) == 7

test_input = { "maxHeights": [5,2,4,4] }
assert my_solution.maximumSumOfHeights(**test_input) == 12

test_input = { "maxHeights": [1,5,5,3,3] }
assert my_solution.maximumSumOfHeights(**test_input) == 17

test_input = { "maxHeights": [3,1,1,4,5,5,4,6] }
assert my_solution.maximumSumOfHeights(**test_input) == 25

test_input = { "maxHeights": [1,4,3,4,5,1] }
assert my_solution.maximumSumOfHeights(**test_input) == 17

test_input = { "maxHeights": [5,5,3,1,1,2,5,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 18

test_input = { "maxHeights": [3,1,3,2,6,1,4,4,6] }
assert my_solution.maximumSumOfHeights(**test_input) == 20

test_input = { "maxHeights": [5,3,3] }
assert my_solution.maximumSumOfHeights(**test_input) == 11

test_input = { "maxHeights": [5,2,1,4,3,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 14

test_input = { "maxHeights": [1,3,2,1] }
assert my_solution.maximumSumOfHeights(**test_input) == 7

test_input = { "maxHeights": [1,3,6] }
assert my_solution.maximumSumOfHeights(**test_input) == 10

test_input = { "maxHeights": [5,5,5,3,3,3,3] }
assert my_solution.maximumSumOfHeights(**test_input) == 27

test_input = { "maxHeights": [1,3,3,2,1,2] }
assert my_solution.maximumSumOfHeights(**test_input) == 11

test_input = { "maxHeights": [5,5,4,1,4,4,5,6,4] }
assert my_solution.maximumSumOfHeights(**test_input) == 27

test_input = { "maxHeights": [3,5,5,6,2] }
assert my_solution.maximumSumOfHeights(**test_input) == 21

test_input = { "maxHeights": [4,6,6,1] }
assert my_solution.maximumSumOfHeights(**test_input) == 17

test_input = { "maxHeights": [4,2,6,1,4,1,5,3,6] }
assert my_solution.maximumSumOfHeights(**test_input) == 18

test_input = { "maxHeights": [4,1,6,3,6,6] }
assert my_solution.maximumSumOfHeights(**test_input) == 20

test_input = { "maxHeights": [5,2,1,4,1,6,1,5,3,4] }
assert my_solution.maximumSumOfHeights(**test_input) == 18

test_input = { "maxHeights": [1,4,6,3,5,1] }
assert my_solution.maximumSumOfHeights(**test_input) == 18

test_input = { "maxHeights": [6,1,2,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 9

test_input = { "maxHeights": [6,1,5,1,6,2,2] }
assert my_solution.maximumSumOfHeights(**test_input) == 14

test_input = { "maxHeights": [6,1,2,3,4,4] }
assert my_solution.maximumSumOfHeights(**test_input) == 15

test_input = { "maxHeights": [6,1,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 8

test_input = { "maxHeights": [1,6,6,3,5,6,1,1] }
assert my_solution.maximumSumOfHeights(**test_input) == 24

test_input = { "maxHeights": [2,6,1,5,1,2,3] }
assert my_solution.maximumSumOfHeights(**test_input) == 13

test_input = { "maxHeights": [3,5,1,6,3,6] }
assert my_solution.maximumSumOfHeights(**test_input) == 15

test_input = { "maxHeights": [4,4,5,3] }
assert my_solution.maximumSumOfHeights(**test_input) == 16

test_input = { "maxHeights": [3,5,4,4,3,1,1,6] }
assert my_solution.maximumSumOfHeights(**test_input) == 22

test_input = { "maxHeights": [5,6,4,4,5,1,2,3,5,6] }
assert my_solution.maximumSumOfHeights(**test_input) == 28

test_input = { "maxHeights": [2,5,1,5,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 13

test_input = { "maxHeights": [1,2,6,2,6,5,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 23

test_input = { "maxHeights": [1,1,6,4,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 16

test_input = { "maxHeights": [3,4,1,6,2] }
assert my_solution.maximumSumOfHeights(**test_input) == 11

test_input = { "maxHeights": [1,3,3,5,6,4,6,5,2,2] }
assert my_solution.maximumSumOfHeights(**test_input) == 34

test_input = { "maxHeights": [2,4,6,4,6,3,1,5,6] }
assert my_solution.maximumSumOfHeights(**test_input) == 26

test_input = { "maxHeights": [1,6,1,6,4] }
assert my_solution.maximumSumOfHeights(**test_input) == 13

test_input = { "maxHeights": [4,2,1] }
assert my_solution.maximumSumOfHeights(**test_input) == 7

test_input = { "maxHeights": [1,2,4,1] }
assert my_solution.maximumSumOfHeights(**test_input) == 8

test_input = { "maxHeights": [1,3,3,2,5,1,4,3,1,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 17

test_input = { "maxHeights": [4,3,1,4] }
assert my_solution.maximumSumOfHeights(**test_input) == 9

test_input = { "maxHeights": [5,1,3,4,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 14

test_input = { "maxHeights": [1,5,4,2] }
assert my_solution.maximumSumOfHeights(**test_input) == 12

test_input = { "maxHeights": [2,6,4,3,2,2,2,5,6,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 30

test_input = { "maxHeights": [2,6,1,2,1,1,2,4] }
assert my_solution.maximumSumOfHeights(**test_input) == 14

test_input = { "maxHeights": [1,2,5,3,3,3,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 20

test_input = { "maxHeights": [2,5,2,2,1] }
assert my_solution.maximumSumOfHeights(**test_input) == 12

test_input = { "maxHeights": [3,5,3,4] }
assert my_solution.maximumSumOfHeights(**test_input) == 14

test_input = { "maxHeights": [4,6,6,3,4,1,6] }
assert my_solution.maximumSumOfHeights(**test_input) == 24

test_input = { "maxHeights": [2,3,5,3,4,1,1,1,3,2] }
assert my_solution.maximumSumOfHeights(**test_input) == 21

test_input = { "maxHeights": [6,6,5,3,5,4,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 29

test_input = { "maxHeights": [5,5,2,2,4,2,3,2,4,4] }
assert my_solution.maximumSumOfHeights(**test_input) == 26

test_input = { "maxHeights": [1,2,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 8

test_input = { "maxHeights": [3,6,2,4,5,2,2,5,1] }
assert my_solution.maximumSumOfHeights(**test_input) == 22

test_input = { "maxHeights": [6,2,6,3,4,6,2] }
assert my_solution.maximumSumOfHeights(**test_input) == 22

test_input = { "maxHeights": [6,2,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 10

test_input = { "maxHeights": [5,4,2,6] }
assert my_solution.maximumSumOfHeights(**test_input) == 13

test_input = { "maxHeights": [2,6,5,3] }
assert my_solution.maximumSumOfHeights(**test_input) == 16

test_input = { "maxHeights": [4,5,4,1,6,5,1,3] }
assert my_solution.maximumSumOfHeights(**test_input) == 18

test_input = { "maxHeights": [4,1,2,4,6,2,6,3] }
assert my_solution.maximumSumOfHeights(**test_input) == 20

test_input = { "maxHeights": [6,4,4,4,2] }
assert my_solution.maximumSumOfHeights(**test_input) == 20

test_input = { "maxHeights": [5,5,4,2] }
assert my_solution.maximumSumOfHeights(**test_input) == 16

test_input = { "maxHeights": [5,3,3,4,2,2,1,4] }
assert my_solution.maximumSumOfHeights(**test_input) == 20

test_input = { "maxHeights": [6,5,6,6,6] }
assert my_solution.maximumSumOfHeights(**test_input) == 28

test_input = { "maxHeights": [6,3,5,6,2,2,3] }
assert my_solution.maximumSumOfHeights(**test_input) == 23

test_input = { "maxHeights": [4,6,4,5] }
assert my_solution.maximumSumOfHeights(**test_input) == 18

test_input = { "maxHeights": [3,5,4,2,1,1,5,6,1] }
assert my_solution.maximumSumOfHeights(**test_input) == 19

test_input = { "maxHeights": [2,3,5,6,2,4] }
assert my_solution.maximumSumOfHeights(**test_input) == 20

test_input = { "maxHeights": [4,5,2,1,4,6,6,1,6,2] }
assert my_solution.maximumSumOfHeights(**test_input) == 23