Burst Balloons

Problem

Given balloon values, return the maximum coins from bursting every balloon, where bursting balloon i earns left * values[i] * right based on its current neighbours, and the outside is treated as value 1.

Use interval dynamic programming with virtual 1s at both ends: for each interval choose which balloon is burst last. Return 0 when there are no balloons.

Hint

Thinking about the last balloon burst in an interval avoids the changing-neighbour problem.

Test cases

case 1

in: [[3,1,5,8]]

expected: 167

case 2

in: [[1,5]]

expected: 10

case 3

in: [[5]]

expected: 5

case 4

in: [[]]

expected: 0

case 5

in: [[1,2,3]]

expected: 12

Starter codePython

def max_coins_balloons(nums):
    # Your code here
    pass

5 test cases · run your code against them in the editor