<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>

def pickUniques(vals):
    cnts = [0]*101
    for v in vals:
        cnts[v[0]] += 1
    for (i,v) in enumerate(vals): 
        if cnts[v[0]] == 1: 
            return pickBox(vals, i)
    return 0, vals
        
def pickBox(vals, i):
    pts = vals[i][1] *  vals[i][1]
    if i == 0 :
        updatedArr = vals[1:]
    elif i == len(vals)-1:
        updatedArr = vals[0:-1]
    else: 
        if vals[i-1][0] == vals[i+1][0] : 
            updatedArr = vals[0:i-1] + [(vals[i+1][0], vals[i-1][1]+vals[i+1][1])] + vals[i+2:]
        else: 
            updatedArr = vals[0:i]+vals[i+1:]
    pts2, udpatedArr2 = pickUniques(updatedArr)
    return pts+pts2, udpatedArr2
    
    


def findMax(vals, start, end, CACHE, start_val_cnt = 0):
    # print("findMax", vals, start, end , start_val_cnt) 
    if end < start : 
        return 0
    if CACHE[start][end][start_val_cnt] != None:
        return CACHE[start][end][start_val_cnt]
    

        
    # Pick start
    pts1 = (vals[start][1]+start_val_cnt) *  (vals[start][1]+start_val_cnt)
    pts1 += findMax(vals, start+1, end, CACHE, 0)
    CACHE[start][end][start_val_cnt] = pts1
    
    if start < end :
        for i in range(start+1, end+1):
            if vals[i][0] == vals[start][0]:
                pts =  findMax(vals, start+1, i-1, CACHE, 0) + findMax(vals, i, end, CACHE, vals[start][1]+start_val_cnt)
                CACHE[start][end][start_val_cnt] = max(CACHE[start][end][start_val_cnt], pts)
    return CACHE[start][end][start_val_cnt]
    


class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        initial = [(boxes[0], 1)]
        for b in boxes[1:]:
            if b == initial[-1][0]:
                initial[-1] = (b, initial[-1][1]+1)
            else: 
                initial.append((b, 1))
        pts, updated = pickUniques(initial)
        CACHE = [[[None]*len(boxes) for _ in range(len(boxes))] for _ in range(len(boxes))]
        return pts + findMax(updated, 0, len(updated)-1, CACHE)
        
        
27200