1190. Burst Balloons

Given balloons with numbers nums, bursting balloon i earns nums[left]*nums[i]*nums[right] coins where left and right are the adjacent unburst balloons (treat out-of-bounds as 1). Return the maximum coins from bursting all balloons. The input is JSON {nums}.

Input: JSON {nums}.

Output: Integer — the maximum coins.

Examples

Input: {"nums":[3,1,5,8]}
Output: 167
Explanation: An optimal burst order yields 167.

Input: {"nums":[1,5]}
Output: 10
Explanation: Burst 1 then 5.

Input: {"nums":[7]}
Output: 7
Explanation: Single balloon.

Constraints

• 1<=n<=300

Asked by