Burst Balloons
You have n balloons in a row, each printed with a number, given as the array nums. Bursting balloon i earns you nums[left] * nums[i] * nums[right] coins, where left and right are the balloons currently adjacent to it (already-burst balloons are gone, so neighbors shift). A missing neighbor off either end counts as a 1.
Burst all the balloons in whatever order you like and return the maximum coins you can collect.
Constraints: 1 <= n <= 300 and 0 <= nums[i] <= 100.
Examples
- Input:
- nums = [3, 1, 5, 8]
- Output:
- 167
Burst 1, then 5, then 3, then 8: 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15 + 120 + 24 + 8 = 167.
- Input:
- nums = [1, 5]
- Output:
- 10
Burst the 1 first (1*1*5 = 5), then the 5 (1*5*1 = 5).
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.