Description
You are given n balloons indexed from 0 to n-1. Each balloon is painted with a number on it represented by nums[i]. You are asked to burst all balloons. If you burst balloon i, you will get nums[i-1] * nums[i] * nums[i+1] coins. If i-1 or i+1 goes out of bounds, treat it as if there is a balloon with 1 painted on it. Return the maximum coins you can collect.
Examples
Input:
nums = [3,1,5,8]Output:
167Explanation:
Burst order: 1,5,3,8. Coins: 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15+120+24+8 = 167.
Input:
nums = [1,5]Output:
10Explanation:
Burst 1 first (1*1*5=5), then 5 (1*5*1=5). Total = 10.
Input:
nums = [2,4,6]Output:
64Explanation:
Burst order matters for optimal coins. Bursting 4 first: 2*4*6=48, then 2: 1*2*6=12, then 6: 1*6*1=6, total=66. The optimal strategy yields 66 coins.
Constraints
- •
n == nums.length - •
1 ≤ n ≤ 300 - •
0 ≤ nums[i] ≤ 100