Burst Balloons
Real-world version: Rail Disc PayoutThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def rail_payout(discs: list[int]) -> int:public int railPayout(int[] discs)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 14 test cases: 14 passed
- Passed: 4 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's