You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.
If you burst the i-th balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, treat it as if there is a balloon with the number 1 painted on it.
Return the maximum coins you can collect by bursting the balloons wisely.
Input: nums = [3, 1, 5, 8] Output: 167 Explanation: Burst order [1, 5, 3, 8] gives 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15 + 120 + 24 + 8 = 167.
Input: nums = [1, 5] Output: 10 Explanation: Burst 1 first (1*1*5 = 5), then burst 5 (1*5*1 = 5). Total = 10.
n == nums.length1 <= n <= 3000 <= nums[i] <= 100nums = [3, 1, 5, 8]