312. Burst Balloons

Practice Burst Balloons for free on NudgeCode: Hard, Dynamic Programming pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Balloons stand in a row, balloon i showing the number nums[i]. Bursting a balloon 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. Burst every balloon and return the most coins you can collect.

Example

nums = [3,1,5,8]  ->  167
  burst 1: 3*1*5 = 15    -> [3,5,8]
  burst 5: 3*5*8 = 120   -> [3,8]
  burst 3: 1*3*8 = 24    -> [8]
  burst 8: 1*8*1 = 8     total 167
nums = [1,5]      ->  10

Constraints