You have n balloons in a row, each painted with a number nums[i]. Bursting balloon i earns nums[i - 1] * nums[i] * nums[i + 1] coins, using its current neighbors; a missing neighbor at either end counts as 1. After a burst, its two neighbors become adjacent.
Return the maximum number of coins you can collect by bursting all the balloons.
Examples
Example 1
- Input
- nums = [3, 1, 5, 8]
- Output
- 167
- Why
- Burst 1, then 5, then 3, then 8: 3·1·5 + 3·5·8 + 1·3·8 + 1·8·1 = 15 + 120 + 24 + 8 = 167.
Example 2
- Input
- nums = [1, 5]
- Output
- 10
Constraints
1 <= nums.length <= 3000 <= nums[i] <= 100