<p>You are given a <strong>0-indexed</strong> array <code>maxHeights</code> of <code>n</code> integers.</p>

<p>You are tasked with building <code>n</code> towers in the coordinate line. The <code>i<sup>th</sup></code> tower is built at coordinate <code>i</code> and has a height of <code>heights[i]</code>.</p>

<p>A configuration of towers is <strong>beautiful</strong> if the following conditions hold:</p>

<ol>
	<li><code>1 &lt;= heights[i] &lt;= maxHeights[i]</code></li>
	<li><code>heights</code> is a <strong>mountain</strong> array.</li>
</ol>

<p>Array <code>heights</code> is a <strong>mountain</strong> if there exists an index <code>i</code> such that:</p>

<ul>
	<li>For all <code>0 &lt; j &lt;= i</code>, <code>heights[j - 1] &lt;= heights[j]</code></li>
	<li>For all <code>i &lt;= k &lt; n - 1</code>, <code>heights[k + 1] &lt;= heights[k]</code></li>
</ul>

<p>Return <em>the <strong>maximum possible sum of heights</strong> of a beautiful configuration of towers</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n == maxHeights.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= maxHeights[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def maximumSumOfHeights(self, maxHeight: List[int]) -> int:
        """
        [Inuition]
        calculate each left mountain up to i, using i as the peak. And calculate the right mountain up to i using i as the peak
        save those into separate arrays
        then we can loop through the array and calcualte the max for left hill + right hill - peak (peak counted twice)
        
        to construct left/right hill for each i as peak, we can use a stack to keep the index of all the element we have seen and less than current i 
        """
        # initialize left hill
        left = []
        #initialize cur hill and stack
        cur = 0
        stack = [-1]
        n = len(maxHeight)
        for i in range(n):
            while len(stack)>1 and maxHeight[stack[-1]]>maxHeight[i]:
                j = stack.pop()
                # we subtract all the height we have added before up to j index
                cur -= (j-stack[-1])*maxHeight[j]
            # we add the current maxhight from the last index where value is less than i
            cur +=(i-stack[-1])*maxHeight[i]
            stack.append(i)
            left.append(cur)
        
        res = 0
        # now we build the right hill
        stack = [n]
        cur = 0
        for i in range(n-1, -1, -1):
            while len(stack)>1 and maxHeight[stack[-1]]>maxHeight[i]:
                j = stack.pop()
                # we subtract all values until the last index that val is less than i
                cur -= (stack[-1]-j)*maxHeight[j]
            # add all values from the last index where value is less than i
            cur += (stack[-1]-i)*maxHeight[i]
            stack.append(i)
            # left hill + right hill (which is cur here) - i_val
            res = max(res, left[i]+cur-maxHeight[i])
            
        return res
            
        
        
        
        
        
        
    
    # my solution. Works but TLE
    # def maximumSumOfHeights(self, maxHeight: List[int]) -> int:
#         """
#         [Enumeration]
#         maxHeights = [1, 2, 3, 4], heights = [1, 2, 3, 3] is beautiful towels. and the sum is 9
        
#         [Intuition]
#         There must be a tip that is not the first or the last element
#         only the one immediate to the left and the right is less or equal to the i's height
#         Maybe we can find the highest maxHeight element and make that the tip to maximize the sum
#         all the ones surrunding that peak is max the peak or the maxHeight
        
#         [Implementation] ->wrong answer
        
#         find the max possible height in maxHeight. That will be the peak
#         return that index
        
#         initialize a res
#         loop through the element to the left of peak:
#             height is the max of last height and maxHeight
#             add height to res
            
#         loop through the element to the left of peak:
#             height is the max of last height and maxHeight
#             add height to res
            
#         return res
#         """
#         res = 0
#         for i, p in enumerate(maxHeight):
#             res = max(res, self.find_b_tower(p, maxHeight, i))
        
#         return res
        

#     def find_b_tower(self, peak, maxHeight, p_idx):
#         # initialize a res
#         res = peak
#         h = peak
#         # loop through the element to the left of peak:
#         for i in range(p_idx-1, -1, -1):
#             # height is the max of last height and maxHeight
#             h = min(h, maxHeight[i])
#             # add height to res
#             res +=h
        
#         h = peak
#         # loop through the element to the left of peak:
#         for i in range(p_idx+1, len(maxHeight)):
#             # height is the max of last height and maxHeight
#             h = min(h, maxHeight[i])
#             # add height to res
#             res +=h
            
#         return res
        
541