0202HardArrayDynamic Programming

Rail Disc Payout

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.

An arcade cabinet holds a straight rail of stamped discs. discs[i] is the number stamped on the disc sitting at position i, counting from the left end of the rail.

You empty the rail one disc at a time. Knocking out a disc pays out the product of three numbers: the disc you knocked out, the disc touching it on its left, and the disc touching it on its right. Every time a disc leaves, the ones still on the rail slide together to close the gap, so a disc's two touching neighbours are whichever discs are beside it at the moment it is knocked out. When a disc has nothing to its left, or nothing to its right, the cabinet scores that empty side as though a disc stamped 1 were sitting there.

You pick the order the discs are knocked out in, and every disc is knocked out. Return the largest total payout you can be left with.

Examples

Example 1

Input: discs = [4, 2, 6]
Output: 78

Take the middle disc first for 4 * 2 * 6 = 48, which leaves 4 and 6 touching. The 4 then pays 1 * 4 * 6 = 24, and the 6 pays 1 * 6 * 1 = 6, adding up to 78.

Example 2

Input: discs = [7, 1, 9, 3]
Output: 280

Knocking out the 1 pays 7 * 1 * 9 = 63, then the 9 pays 7 * 9 * 3 = 189, then the 3 pays 7 * 3 * 1 = 21, and the 7 pays 1 * 7 * 1 = 7. Those four payouts total 280.

Example 3

Input: discs = [5]
Output: 5

The lone disc has nothing on either side, so both sides score as 1 and the single payout is 1 * 5 * 1 = 5.

Example 4

Input: discs = [0, 5, 0]
Output: 5

Knock out the left 0 for 1 * 0 * 5 = 0 and the right 0 for 5 * 0 * 1 = 0, which leaves the 5 alone on the rail to pay 1 * 5 * 1 = 5. The three payouts total 5.

Constraints

n == discs.length
1 <= n <= 300
0 <= discs[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 rail_payout(discs: list[int]) -> int:

Java

public int railPayout(int[] discs)

The intended approach

Time O(n^3)Space O(n^2)

Pad a 1 onto each end of the rail so every disc has a neighbour, then reason about a stretch of the rail bounded by two padding positions and ask which disc inside it is knocked out last. At that moment the only discs left touching it are the two bounding ones, so its payout is fixed, and the discs on either side of it never interact, which splits the stretch into two smaller stretches of the same shape. Fill a table over stretches in order of increasing width, trying every interior disc as the last one out, and read the whole padded rail off the final entry.

Pythonentry point: rail_payout

def rail_payout(discs):
    # Time O(n^3): one pass per stretch width, and every disc tried as the last
    # pop inside each stretch. Space O(n^2) for the stretch table.
    padded = [1] + list(discs) + [1]
    n = len(padded)
    best = [[0] * n for _ in range(n)]
    for width in range(2, n):
        for lo in range(0, n - width):
            hi = lo + width
            top = 0
            for last in range(lo + 1, hi):
                total = (best[lo][last] + best[last][hi]
                         + padded[lo] * padded[last] * padded[hi])
                if total > top:
                    top = total
            best[lo][hi] = top
    return best[0][n - 1]

The obvious version

Simulate the cabinet directly: from a given set of discs still on the rail, try knocking out each one next and recurse on what remains, memoising on the set of survivors. Exponential in n, exact for small rails.

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_rail_payout(discs):
    from functools import lru_cache
    values = list(discs)

    @lru_cache(maxsize=None)
    def best(rail):
        if not rail:
            return 0
        top = 0
        for pos in range(len(rail)):
            left = values[rail[pos - 1]] if pos > 0 else 1
            right = values[rail[pos + 1]] if pos + 1 < len(rail) else 1
            payout = left * values[rail[pos]] * right
            total = payout + best(rail[:pos] + rail[pos + 1:])
            if total > top:
                top = total
        return top

    return best(tuple(range(len(values))))

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
4 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