DSA problem
Remove Boxes
You are given an array of boxes, where each entry is a positive integer color. You may repeatedly remove a contiguous run of boxes of the same color, gaining k * k points if the run has length k. The remaining boxes close up after each removal. Return the maximum number of points you can collect after removing every box.
The naive greedy "always remove the longest current run" is wrong: sometimes it pays to leave a run intact so that later, two split runs of the same color reunite into a longer run. Quadratic scoring means combining a 3-run with a 2-run after deletions in between can yield 5^2 = 25 rather than 3^2 + 2^2 = 13.
The classic DP is three-dimensional. Define dp[i][j][k] = maximum score from boxes [i..j] when there are k additional boxes of the same color as boxes[i] already attached to the left of i (a "prefix" of equal color that will be removed together when the i-run is eventually removed). Two recurrences:
- Remove the prefix run with
boxes[i]: pay(k + 1)^2for thosek + 1boxes, then recurse ondp[i + 1][j][0]. - For each
min(i, j]withboxes[m] == boxes[i], instead of taking the prefix now, splice the boxes(i, m)away first and merge with the m-run:dp[i + 1][m - 1][0] + dp[m][j][k + 1].
Take the maximum of all options. Memoize. The answer is dp[0][n - 1][0]. With memoization, the complexity is bounded by O(n^4) time and O(n^3) space — tight but practical for the constraint n <= 100.
Examples
boxes = [1,3,2,2,2,3,4,3,1]23boxes = [1,1,1]9boxes = [1]1Constraints
- 1 <= boxes.length <= 100
- 1 <= boxes[i] <= 100
- Removing a run of length `k` gives `k * k` points.
- After removal the remaining boxes shift to close the gap.
- You must remove every box.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.