We have an array of colored boxes, and we want to remove them in groups of consecutive same-colored boxes to maximize our total score. The scoring is quadratic: removing k boxes at once gives k*k points, not just k. That means it is always better to remove a larger group at once than to remove the same boxes in smaller batches (for example, removing 4 at once gives 16 points, while removing 2 + 2 gives only 8).

This quadratic scoring is what makes the problem tricky. It creates an incentive to delay removing boxes so that separated groups of the same color can be merged together. In Example 1, the three 2s are already adjacent, so we remove them first. But the three 3s are scattered at positions 1, 5, and 7. By removing the boxes between them, we can eventually merge them into one group and remove them together for 9 points instead of 1+1+1 = 3 points.

The order of removals decides the total points, and each removal changes which boxes remain for later removals. That dependency between decisions points to dynamic programming. The difficulty is defining a state that captures enough of the past to make optimal choices.

Key Constraints:

Intuition

Try every possible removal order and keep the best total. At each step, scan the array for maximal runs of same-colored boxes. Remove one run, add its score, then recurse on the shorter array that remains. Backtracking over all of these choices finds the maximum.

This simulates the process directly, with no special state representation. It establishes a correct baseline and shows why the obvious formulation is too slow, which motivates the DP that follows.

Algorithm

Example Walkthrough

Code

The brute force re-explores the same configurations many times, since different removal orders lead to identical remaining arrays. A 2D interval DP dp[l][r] would memoize those subproblems, but it fails here: the score of removing boxes[l] depends on how many same-colored boxes outside [l, r] have already merged onto it, and dp[l][r] cannot represent that. The next approach adds a third dimension to carry exactly that information.

Intuition

The DP state gains a third dimension:

dp[l][r][k] = the maximum points from removing boxes[l..r], given that k extra boxes of the same color as boxes[l] are already attached to its left, waiting to be removed together with it.

The k parameter encodes the merging that happens outside the current range. By the time we solve [l, r], earlier removals may have brought same-colored boxes adjacent to boxes[l]. Those boxes are no longer in the array, but their count affects the score we get when we finally remove boxes[l], so the state must carry it.

For any state dp[l][r][k], there are two options:

Option 1: Remove boxes[l] immediately. We remove boxes[l] together with the k extra boxes attached to it. That gives us (k+1)^2 points (k extras + boxes[l] itself = k+1 boxes total). Then we solve dp[l+1][r][0] for the remaining range.

Option 2: Find a matching box and merge. We look for some index m in (l, r] where boxes[m] == boxes[l]. If we first remove everything between l+1 and m-1 (which gives dp[l+1][m-1][0] points), then boxes[m] becomes adjacent to where boxes[l] was. Now we can treat boxes[l] as one more "extra" box attached to boxes[m]. So we solve dp[m][r][k+1].

We take the maximum across all these choices.

Algorithm

Example Walkthrough

Code