Burst Balloons
HardP3Coding
There are n balloons in a row, balloon i painted with the number nums[i]. Bursting balloon i earns left * nums[i] * right coins, where left and right are the numbers on its current neighbours after earlier bursts. A neighbour that does not exist counts as the number 1.
Burst all the balloons in the best order and return the maximum coins you can collect.
Example 1
- Input
- nums = [3,1,5,8]
- Output
- 167
- Why
- Burst 1, 5, 3, then 8 for 15 + 120 + 24 + 8 = 167.
Example 2
- Input
- nums = [1,5]
- Output
- 10
- Why
- Burst 1 first (1*1*5 = 5) then 5 (1*5*1 = 5), or in the other order: total 10.
Example 3
- Input
- nums = [7]
- Output
- 7
Constraints
- 0 <= nums.length <= 300
- 0 <= nums[i] <= 100
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 10. ⌘Enter runs, ⌘⇧Enter submits.