hard

Burst Balloons

You have a row of balloons with numbers on them. Bursting balloon i earns nums[i-1] * nums[i] * nums[i+1] coins, where the boundaries count as 1, and the remaining balloons close ranks. Find the maximum coins obtainable by bursting all balloons in some order.

Constraints

1 ≤ n ≤ 300
0 ≤ nums[i] ≤ 100

Examples

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

out: 167

Code it yourself

Solve in

Your python code

Test execution is not yet available for this exercise.Practice journal →Draft saved in this browser.

Hints:

Which approach applies?

Choose an approach to check your pattern recognition, or reveal the discussion when you need help.