hardDynamic Programming 2DPure DSA~50 min
Remove Colored Boxes for Maximum Points
A conveyor holds colored boxes in a row. Removing a contiguous run of k same-colored boxes scores k*k points and closes the gap. Maximize total points by choosing the removal order.
Problem
Given an array boxes where boxes[i] is the color of the i-th box, repeatedly remove a contiguous group of boxes of the same color. Removing a group of k boxes earns k*k points. Return the maximum points obtainable by removing all boxes in some order.
Input
An integer array boxes of length [1, 100] with color values in [1, 100].
Output
An integer: the maximum total points.
Constraints
- 1 <= boxes.length <= 100
- 1 <= boxes[i] <= 100
Examples
Example 1
Input
boxes = [1,3,2,2,2,3,4,3,1]
Output
23
Optimal removals achieve 23 points.
Example 2
Input
boxes = [1,1,1]
Output
9
Remove all three at once: 3*3 = 9.