A row of balloons has numbers nums. Bursting balloon i earns left * nums[i] * right, where left and right are the numbers on its current neighbours (a missing neighbour past either end counts as 1). After a burst, the balloon is gone and its neighbours become adjacent. You burst every balloon, in any order you choose.
Write max_coins(nums: list[int]) -> int: the most coins you can earn.
Examples:
max_coins([2, 4, 3]) == 33: burst4first (2·4·3 = 24), leaving[2, 3]; burst2(1·2·3 = 6); burst3(1·3·1 = 3).max_coins([5]) == 5max_coins([]) == 0
Constraints: 0 <= len(nums) <= 100, 0 <= nums[i] <= 100. Trying every order is n!; aim for O(n³).
Hint: pad the row with a 1 on each end. If k is the last balloon burst strictly between l and r, it earns vals[l] * vals[k] * vals[r], and the two sides of k are now independent subproblems.
Show hint
choosing which balloon to burst first in a range leaves two halves that still affect each other. Think instead about which balloon in a range is burst last.