Given an integer array balloon_values of length n, where each element represents the value of a balloon, you must burst all balloons. When bursting the k-th balloon, you gain balloon_values[k-1] * balloon_values[k] * balloon_values[k+1] coins. If k-1 or k+1 is out of bounds, treat the value as 1. Return the maximum total coins obtainable by bursting the balloons in an optimal order.
Example 1
Input: [2,4,7]
Output: 56
Explanation: Burst order: 4 -> 2 -> 7. Coins: 2*4*7=56, then 1*2*7=14, then 1*7*1=7. Optimal order yields 56.
Example 2
Input: [6,2,9,3]
Output: 162
Explanation: Optimal bursting order yields 162 coins.
Constraints
Case 1
Input: [5,1,3]
Expected: 35
Case 2
Input: [8,2]
Expected: 32
Case 3
Input: [1,1,1,1]
Expected: 4
Case 4
Input: [10]
Expected: 10
Case 5
Input: [0,5,0]
Expected: 5