Burst Balloons

Hard

You have n balloons with numbers in nums. Bursting balloon i gives nums[i-1]*nums[i]*nums[i+1] coins (treat out-of-range as 1). Return the maximum coins from bursting all balloons.

Example 1

Input:  nums = [3,1,5,8]
Output: 167

Example 2

Input:  nums = [1,5]
Output: 10

Constraints

• 1 <= n <= 300
• 0 <= nums[i] <= 100