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

"""
Non-obivous grouping: 
3232232223431
Brutforce: O(2**N)
DP on subsegments.
Potentially updating partially calculated score for group
Score function k *k = 1 + 3 + 5 + ... + 2*k - 1
Adding k-th element to same group increases score by 2*k - 1

dp[left, right, k] - answer for [left, right) where last element is removed along with group of size k
dp_max[left, right] = max(dp[left, right, k])
previous[right] - last occurence of element which lies in index r

dp[left, left, k] = 0
dp[left, right, 1] = dp_max[left, right - 1] + 1
k >= 2, 
    prevous[right] >= left: 
        dp[left, right, k] = 
            dp[left, prevous[right], k - 1] 
            + dp_max[previous[right] + 1, right] 
            + (2 * k - 1)
    prevous[right] < left: 
        dp[l, r, k] = -INF

ans = dpm[0, n]
"""
class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        n = len(boxes)
        INF = 1e9

        dp = [[[-INF for _ in range(n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]
        dp_max = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

        for left in range(n):
            for k in range(n + 1):
                dp[left][left][k] = 0
        
        for length in range(1, n + 1):
            for left in range(0, n - length + 1):
                right = left + length
                dp_max[left][right] = dp[left][right][1] = dp_max[left][right - 1] + 1
                indices = []
                for idx in range(left, right - 1):
                    if boxes[idx] == boxes[right - 1]:
                        indices.append(idx)
                for k in range(2, len(indices) + 2):
                    for prev in indices[k - 2:]:
                        if left > prev:
                            continue
                        candidate = (
                            dp[left][prev + 1][k - 1]
                            + dp_max[prev + 1][right - 1]
                            + 2 * k - 1
                        )
                        dp[left][right][k] = max(dp[left][right][k], candidate)
                    dp_max[left][right] = max(dp_max[left][right], dp[left][right][k])
        
        return dp_max[0][n]

58400