<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 maximumSumOfHeights(self, heights: List[int]) -> int:
        """
        - Try every element as peak
        - Keep mono decreasing stack of preceding elements, copy over
        """
        if len(heights) < 1:
            return 0
        elif len(heights) == 1:
            return heights[0]

        total = sum(heights)
        # print(total)

        min_cost_peak = 0
        min_seen = heights[0]
        peaks: List[List[List[int], int]] = [[[heights[0]], 0]]
        for i in range(1, len(heights)):
            h = heights[i]
            min_seen = min(h, min_seen)


            new_p = [[h for _ in range(i + 1)], 0]
            for j in range(i-1, -1, -1):
                el = heights[j]
                follow = new_p[0][j + 1]
                # print(el, follow)
                if el > follow:
                    new_p[0][j] = follow
                    new_p[1] += el - follow
                else:
                    new_p[0][j] = el

            
            peaks.append(new_p)

            for j in range(len(peaks) - 1):
                p = peaks[j]
                last_el = p[0][-1]
                if h > last_el:
                    p[0].append(last_el)
                    p[1] += h - last_el
                else:
                    p[0].append(h)

            min_cost_peak = 0
            for i,p in enumerate(peaks):
                if p[1] < peaks[min_cost_peak][1]:
                    min_cost_peak = i


        # print(peaks)

        min_removed = total
        for peak in peaks:
            if peak[1] < min_removed:
                min_removed = peak[1]

        return total - min_removed


    def maximumSumOfHeightsOld(self, heights: List[int]) -> int:
        """
        [9,8,3,10,3,3,3]
        10 | [9] 0 | [9,8,3] 0
           | [9,10] | [10] 

        - ID potential peaks: inc before, dec after
        [9,8,3,10,3,3,3]
        {
            9: ([], 0),
        }
        {
            9: ([8,3], 0),
        }
        {
            9: ([8,3,3], 7), 10->3
            10: ([], 11) 9->3, 8->3
        }
        """
        if len(heights) < 1:
            return 0
        elif len(heights) == 1:
            return heights[0]

        total = sum(heights)
        print(total)

        peaks: List[tuple[List[int], int]] = [[[heights[0]], 0]]
        for i in range(1, len(heights)):
            h = heights[i]
            
            pidx = -1
            for i,p in enumerate(peaks):
                last_el = p[0][-1]
                if h > last_el:
                    pidx = i
                    p[0].append(last_el)
                    p[1] += h - last_el
                else:
                    p[0].append(h)

            if pidx != -1:
                p = peaks[pidx]
                last_el = p[0][-1]
                cost = p[1]
                asc = []
                for i, el in enumerate(p[0]):
                    if el > last_el:
                        cost += el - last_el
                        asc.append(last_el)
                    else:
                        asc.append(el)
                peaks.append([asc, cost])
            
            # last_el = peaks[-1][0][-1]
            # if h > last_el:
            #     cost = peaks[-1][1]
            #     for el in peaks[-1][0]:
            #         cost += el - last_el
            #     new_peak = [[h], cost]

            #     bricks_removed = h - last_el
            #     for peak in peaks:
            #         peak[0].append(last_el)
            #         peak[1] += bricks_removed

            #     peaks.append(new_peak)
            # else:
            #     for peak in peaks:
            #         peak[0].append(h)

        print(peaks)

        min_removed = total
        for peak in peaks:
            if peak[1] < min_removed:
                min_removed = peak[1]

        return total - min_removed

1695