At a fair, n balloons hang in a row. Balloon i has the number nums[i] written on it. You must pop every balloon, one at a time.
When you pop balloon i, you earn left * nums[i] * right coins. Here left and right are the numbers on the balloons that are still not popped and are next to balloon i. If there is no balloon on one side, use 1 for that side.
Pop the balloons in the best order. Return the largest number of coins you can earn.
Examples
Example 1:
Input: nums = [2,4,3]
Output: 33
Explanation: Pop 4 first: 2*4*3 = 24. Then pop 2: 1*2*3 = 6. Then pop 3: 1*3*1 = 3. Total 33.
Example 2:
Input: nums = [4,7]
Output: 35
Explanation: Pop 4 first: 1 * 4 * 7 = 28. Then pop 7: 1 * 7 * 1 = 7. The total is 35.
Example 3:
Input: nums = [1,6,2,3]
Output: 66
Explanation: Pop 1, 2, 3 and 6 in this order: 6 + 36 + 18 + 6 = 66.