<p>You are given an array <code>heights</code> of <code>n</code> integers representing the number of bricks in <code>n</code> consecutive towers. Your task is to remove some bricks to form a <strong>mountain-shaped</strong> 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.</p>

<p>Return the <strong>maximum possible sum</strong> of heights of a mountain-shaped tower arrangement.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">heights = [5,3,4,1,1]</span></p>

<p><strong>Output:</strong> <span class="example-io">13</span></p>

<p><strong>Explanation:</strong></p>

<p>We remove some bricks to make <code>heights =&nbsp;[5,3,3,1,1]</code>, the peak is at index 0.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">heights = [6,5,3,9,2,7]</span></p>

<p><strong>Output:</strong> <span class="example-io">22</span></p>

<p><strong>Explanation:</strong></p>

<p>We remove some bricks to make <code>heights =&nbsp;[3,3,3,9,2,2]</code>, the peak is at index 3.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">heights = [3,2,5,5,2,3]</span></p>

<p><strong>Output:</strong> <span class="example-io">18</span></p>

<p><strong>Explanation:</strong></p>

<p>We remove some bricks to make <code>heights = [2,2,5,5,2,2]</code>, the peak is at index 2 or 3.</p>
</div>

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

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

class Solution:
    """
    def compute_lhs(self, peak_i, heights):
        lhs = 0
        before_peak = heights[:peak_i + 1]
        for i in range(len(before_peak) - 2, -1, -1):
            if before_peak[i] > before_peak[i + 1]:
                before_peak[i] = before_peak[i + 1]
            lhs += before_peak[i]
        return lhs

    def compute_rhs(self, peak_i, heights):
        rhs = 0
        after_peak = heights[peak_i:]
        for dec_i in range(1, len(after_peak)):
            if after_peak[dec_i] > after_peak[dec_i - 1]:
                after_peak[dec_i] = after_peak[dec_i - 1]
            rhs += after_peak[dec_i]
        return rhs

    def maximumSumOfHeights(self, heights: List[int]) -> int:
        max_sum = 0
        # for i in range(len(heights)):
            # max_sum = max(max_sum, self.getMaxSumWithPeak(heights, i))

        old_peak = 0
        lhs = 0
        rhs = 0
        for i, peak in enumerate(heights):
            # have to update lhs and rhs with new peak
            lhs += old_peak
            rhs -= peak
            if peak > old_peak:  # can reuse lhs
                rhs = self.compute_rhs(i, heights)
            elif peak < old_peak:  # can reuse rhs
                lhs = self.compute_lhs(i, heights)
            max_sum = max(max_sum, lhs + peak + rhs)
            old_peak = peak
        return max_sum
    """

    def getMaxSumWithPeak(self, heights: List[int], peak_i: int) -> int:
        n = len(heights)
        peak = heights[peak_i]

        my_sum = peak
        mountain = [peak] * n

        for i in range(peak_i - 1, -1, -1):
            mountain[i] = min(heights[i], mountain[i+1])
            my_sum += mountain[i]

        for i in range(peak_i + 1, n):
            mountain[i] = min(heights[i], mountain[i-1])
            my_sum += mountain[i]

        return my_sum

    def maximumSumOfHeights(self, heights: List[int]) -> int:
        max_sum = 0
        for i in range(len(heights)):
            max_sum = max(max_sum, self.getMaxSumWithPeak(heights, i))
        return max_sum
        
1748