Show problems as
Classic problem #546HardArrayDynamic ProgrammingMemoization

Remove Boxes

Real-world version: Carton Sweep Score
Tracked in this browser only
Read Remove Boxes on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A conveyor carries a row of cartons, and cartons[i] is the colour code printed on the carton at position i.

You empty the conveyor one sweep at a time. A sweep picks any run of neighbouring cartons that all print the same colour code and lifts the whole run off, scoring k * k points where k is the number of cartons that sweep lifted. Everything still on the belt then closes up, so two cartons that were held apart only by the lifted run become neighbours.

Sweep until the belt is bare, and return the highest total score the sweeps can add up to.

Examples

Example 1

Input
cartons = [2,5,5,2]
Output
8

Lifting the run of two 5s scores 4 and leaves the two 2s side by side, and lifting those as one run of two scores another 4, for 8.

Example 2

Input
cartons = [4,4,4,4]
Output
16

All four cartons print the same code and already sit together, so one sweep of four scores 4 * 4 = 16.

Example 3

Input
cartons = [7]
Output
1

One carton means one sweep of size 1, scoring 1 * 1 = 1.

Example 4

Input
cartons = [3,6,3,6,3]
Output
11

Lifting the 6 at position 1 on its own scores 1, then the 6 now at position 2 scores another 1, and the three 3s left behind form one run for 9, giving 11.

Example 5

Input
cartons = [8,9,9,8,8]
Output
13

Lifting the run of two 9s scores 4 and closes the three 8s into one run, which scores 9, giving 13.

Constraints

  • 1 <= cartons.length <= 100
  • 1 <= cartons[i] <= 100

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def remove_boxes(cartons: list[int]) -> int:
Java
public int removeBoxes(int[] cartons)

More on the same topics