<p>You are given several <code>boxes</code> with different colors represented by different positive numbers.</p>

<p>You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (i.e., composed of <code>k</code> boxes, <code>k &gt;= 1</code>), remove them and get <code>k * k</code> points.</p>

<p>Return <em>the maximum points you can get</em>.</p>

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

<pre>
<strong>Input:</strong> boxes = [1,3,2,2,2,3,4,3,1]
<strong>Output:</strong> 23
<strong>Explanation:</strong>
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----&gt; [1, 3, 3, 4, 3, 1] (3*3=9 points) 
----&gt; [1, 3, 3, 3, 1] (1*1=1 points) 
----&gt; [1, 1] (3*3=9 points) 
----&gt; [] (2*2=4 points)
</pre>

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

<pre>
<strong>Input:</strong> boxes = [1,1,1]
<strong>Output:</strong> 9
</pre>

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

<pre>
<strong>Input:</strong> boxes = [1]
<strong>Output:</strong> 1
</pre>

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

<ul>
	<li><code>1 &lt;= boxes.length &lt;= 100</code></li>
	<li><code>1 &lt;= boxes[i]&nbsp;&lt;= 100</code></li>
</ul>

# "likes": 2254,
# "dislikes": 125,

class Solution:
    def removeBoxes(self, boxes: List[int]):
        memo = {}        
        return remove_boxes(memo, boxes, 0, len(boxes) - 1, 0)

def remove_boxes(memo: Dict[Tuple[int,int,int], int], boxes: List[int], low: int, high: int, k: int) -> int:
    key = (low, high, k)
    if key in memo:
        return memo[key]
    
    if high < low:
        # no boxes in between low and high
        return 0
    if low == high:
        return (k + 1) ** 2
    
    # remove box at low
    while low < high and boxes[low] == boxes[low + 1]:
        k += 1
        low += 1

    result = (k + 1) ** 2 + remove_boxes(memo, boxes, low + 1, high, 0)
    for m in range(low + 1, high + 1):
        # find other boxes in range (low, high]
        #   that can be combined with boxes removed at low
        #   to increase points
        if boxes[m] != boxes[low]:
            continue
        points = remove_boxes(memo, boxes, low + 1, m - 1, 0) + remove_boxes(memo, boxes, m, high, k + 1)
        result = max(result, points)
    
    memo[key] = result
    return result



class SolutionFast:
    def removeBoxes(self, boxes: List[int]) -> int:
        box_segments = []
        for box in boxes:
            if len(box_segments) == 0 or box_segments[-1][0] != box:
                box_segments.append((box, 1))
            else:
                box_segments[-1] = (box_segments[-1][0], box_segments[-1][1] + 1)
        # print("boxes =", box_segments)
        memo = {}
        max_score = 0
        for i in range(len(box_segments)):
            last_box, score = self.remove_boxes(memo, box_segments, 0, len(box_segments), i)
            # print("last_box =", last_box, "final score =", score)
            max_score = max(max_score, score + last_box[1] ** 2)
        return max_score

    # A3 B1 C1 A1 D1 E1 A2
    # (A3)(B1C1A1D1E1A2)
    # (A3)((B1C1)(A1)(D1E1A2))
    # (A3)((B1C1)(A1)((D1E1)(A2)))
    # (A3)((A1)(A1))
    # (A3)(A2)
    # (A5)

    # (A3B1C1)A9D1E1A2
    # (A3B1C4)A9D1E1A2
    # (A3+2) vs (A3+2)
    # how to choose between
    # (A3+2)A1
    # (B1+11)A1
    # (C1+11)A1

    # A1B1A1B1A1B1

    # (A1)(B1(A1)B1A1B1)

    # A3B1A3(B10)
    # (A3)B1A3 -> A3+(B1)A3 = A3+(B1)9 = A3+(1)9 = A3+10 ~ 9+10 = 19
    #         vs. A3+B1(A3) = A3+1(A3) = A6+1 ~ 36+1 = 37 (winner)
    #         later A6+1 + B1 = 37+B1 ~ 38
    # A3(B1)A3 -> 9(B1)9 = B1+18
    #         later B1+19 + B11 = B12+19 ~ 144+19 = 163
    # 
    # A2 B1 A1 B2 A2 B1

    # A1 C1 B3 C1 D1 C1 A1
    # A1 (C1 B3 C1 D1 C1 A1)
    # A1 (C1 (B3 C1 D1 C1 A1))
    # A1 (C1 (B3 C1 D1 C1 A1))
    # A1 (C1 ((B3 C1 D1) C1 (A1))))
    # A1 (C1 (((B3) C1 (D1)) C1 (A1))))
    #               vs.
    # A1 (C1 ((B3 (C1 D1)) C1 (A1))))

    def remove_boxes(self, memo: Dict, boxes: List[Tuple[int,int]], i: int, j: int, k: int, depth: int = 0):
        # remove boxes segments between i up to j, leaving k as the last box segment
        # return max points from removing the boxes
        key = (i, j, k)
        if key in memo:
            return memo[key]
        # print(" " * depth, "range=", (i, j), "k=", k)

        result = (None, 0)
        if i >= j:
            # print("ERROR")
            result = (None, 0)
        elif j - i == 1:
            result = (boxes[i], 0)
        elif j - i == 2:
            if k == i:
                result = (boxes[i], boxes[i + 1][1] ** 2)
            else:
                result = (boxes[i + 1], boxes[i][1] ** 2)
        else:
            # k is the fixed boxed
            before_range = range(i, k)
            after_range = range(k + 1, j)
            # print(" " * depth, "  before", before_range)
            # print(" " * depth, "  after", after_range)
            before_results = []
            for before_k in before_range:
                before_results.append(self.remove_boxes(memo, boxes, i, k, before_k, depth + 1))
            after_results = []
            for after_k in after_range:
                after_results.append(self.remove_boxes(memo, boxes, k + 1, j, after_k, depth + 1))
            # print(" "  * depth, "[combining]", "range=", (i, j), "k=", k, "box=", boxes[k], "before=", before_results, "after=", after_results)
            # return the highest score from adding up the scores from before and after and 
            # either selecting the before/after boxes and adding that to the score
            # or adding the before/after boxes and returning the final 
            # determine by highest potential score by summing 
            max_score = 0
            result_real_score = 0
            result_box = box_k = boxes[k]
            if len(before_results) > 0 and len(after_results) > 0:
                # TODO find combination of a before result + after result + box k that's the highest score
                for before_result in before_results:
                    # tally up the score of before + box k
                    before_box, before_score = before_result
                    before_real_score = before_score
                    before_combined_box = box_k
                    if before_box[0] == before_combined_box[0]:
                        # box can be combine with box k
                        before_combined_box = (before_combined_box[0], before_combined_box[1] + before_box[1])
                    else:
                        # box cannot be combined with box k so just count the points from it
                        before_real_score += before_box[1] ** 2

                    for after_result in after_results:
                        after_box, after_score = after_result
                        after_real_score = before_real_score + after_score
                        combined_box = before_combined_box
                        if after_box[0] == combined_box[0]:
                            combined_box = (combined_box[0], combined_box[1] + after_box[1])
                            potential_score = (after_real_score + combined_box[1] ** 2)
                            if max_score < potential_score:
                                max_score = potential_score
                                result_real_score = after_real_score
                                result_box = combined_box
                                # print("result_box both before", result_box)
                        else:
                            after_real_score += after_box[1] ** 2
                            if max_score < after_real_score:
                                max_score = after_real_score
                                result_real_score = after_real_score
                                result_box = combined_box

            elif len(before_results) > 0:
                # TODO find a before result that's the highest score if combine with box k when it's the same color
                for before_result in before_results:
                    # tally up the score of before + box k
                    before_box, before_score = before_result
                    before_real_score = before_score
                    combined_box = box_k
                    if before_box[0] == combined_box[0]:
                        # box can be combine with box k
                        combined_box = (combined_box[0], combined_box[1] + before_box[1])
                        potential_score = before_real_score + combined_box[1] ** 2
                        if max_score < potential_score:
                            max_score = potential_score
                            result_real_score = before_real_score
                            result_box = combined_box
                            # print("result_box before", result_box)
                    else:
                        # box cannot be combined with box k so just count the points from it
                        before_real_score += before_box[1] ** 2
                        if max_score < before_real_score:
                            max_score = before_real_score
                            result_real_score = before_real_score
                            result_box = combined_box                    

            elif len(after_results) > 0:
                # TODO find an after result that's the highest score if combine with box k when it's the same color
                for after_result in after_results:
                    after_box, after_score = after_result
                    after_real_score = after_score
                    combined_box = box_k
                    if after_box[0] == combined_box[0]:
                        combined_box = (combined_box[0], combined_box[1] + after_box[1])
                        potential_score = (after_real_score + combined_box[1] ** 2)
                        if max_score < potential_score:
                            max_score = potential_score
                            result_real_score = after_real_score
                            result_box = combined_box
                            # print("result_box after", result_box)
                    else:
                        after_real_score += after_box[1] ** 2
                        if max_score < after_real_score:
                            max_score = after_real_score
                            result_real_score = after_real_score
                            result_box = combined_box

            result = (result_box, result_real_score)
        # print(" " * depth, "[result]", "range=", (i, j), "k=", k, "box=", boxes[k], "last =", result[0], "score=", result[1])
        memo[key] = result
        return result
28800