118. Burst Balloons

You are given n balloons numbered 0 to n-1 by array nums. If you burst balloon i, you get nums[i-1]*nums[i]*nums[i+1] coins. Missing boundaries equal 1. Find maximum coins by bursting all balloons.

Input: Integer array nums of balloon values.

Output: Integer — maximum coins obtainable.

Examples

Input: [3,1,5,8]
Output: 167
Explanation: Burst 1→3*1*5=15. Burst 5→3*5*8=120. Burst 3→1*3*8=24. Burst 8→1*8*1=8. 15+120+24+8=167.

Input: [1,5]
Output: 10
Explanation: Burst 1→1*1*5=5. Burst 5→1*5*1=5. Total=10.

Input: [2]
Output: 2
Explanation: Burst 2→1*2*1=2.

Constraints

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

Asked by