0405HardArrayDynamic ProgrammingMemoization

Carton Sweep Score

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def remove_boxes(cartons: list[int]) -> int:

Java

public int removeBoxes(int[] cartons)

The intended approach

Time O(n^4) in the worst caseSpace O(n^3) for the memo plus O(n) recursion stack

Score a window `cartons[lo..hi]` together with a count of cartons already set aside that share the colour of `cartons[hi]`, which is the state the memo is keyed on. Either the right end plus everything set aside is swept now, scoring the square of that group and leaving the window one shorter, or some earlier position holding the same colour is joined to the group by first clearing everything strictly between them. Take the better of those over every such position.

Pythonentry point: remove_boxes

import sys


def remove_boxes(cartons):
    # Time O(n^4) worst case: O(n^3) memo keys, each scanning O(n) split
    # points. Space O(n^3) for the memo, plus O(n) for the recursion stack,
    # which stays shallow because every call shrinks the window it works on.
    sys.setrecursionlimit(10000)
    n = len(cartons)
    memo = {}

    def best(lo, hi, carried):
        if lo > hi:
            return 0
        while hi > lo and cartons[hi - 1] == cartons[hi]:
            hi -= 1
            carried += 1
        key = (lo, hi, carried)
        if key in memo:
            return memo[key]
        top = best(lo, hi - 1, 0) + (carried + 1) * (carried + 1)
        for cut in range(lo, hi - 1):
            if cartons[cut] == cartons[hi] and cartons[cut + 1] != cartons[hi]:
                joined = best(cut + 1, hi - 1, 0) + best(lo, cut, carried + 1)
                if joined > top:
                    top = joined
        memo[key] = top
        return top

    return best(0, n - 1, 0)

The obvious version

Search over belt states directly: from a given row, try lifting every possible run of one colour at every length, recurse on what is left, and memoise on the row itself.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_remove_boxes(cartons):
    memo = {}

    def best(state):
        if not state:
            return 0
        if state in memo:
            return memo[state]
        top = 0
        n = len(state)
        i = 0
        while i < n:
            j = i
            while j + 1 < n and state[j + 1] == state[i]:
                j += 1
            for taken in range(1, j - i + 2):
                rest = state[:i] + state[i + taken:]
                score = taken * taken + best(rest)
                if score > top:
                    top = score
            i = j + 1
        memo[state] = top
        return top

    return best(tuple(cartons))

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
5 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in