Burst Balloons
HardDynamic Programming
You are given a row of balloons, where nums[i] is the number painted on balloon i. You must burst every balloon, one at a time, in any order you choose.
When you burst a balloon with value x, you earn left * x * right coins, where left and right are the values of the nearest balloons that are still unburst to its left and right at that moment. If there is no unburst balloon on a side, treat that side's value as 1. After a balloon bursts, its former neighbours become adjacent to each other.
Return the maximum total number of coins you can earn.
Example 1
- Input:
- nums = [3, 2, 5]
- Output:
- 50
- Explanation
- Burst the
2first while it sits between3and5(3 * 2 * 5 = 30), then the3with only the5to its right (1 * 3 * 5 = 15), then the5alone (1 * 5 * 1 = 5). The total is 30 + 15 + 5 = 50.
Example 2
- Input:
- nums = [2, 1, 3, 4]
- Output:
- 42
- Explanation
- One best order is
1(2 * 1 * 3 = 6), then3(2 * 3 * 4 = 24), then2(1 * 2 * 4 = 8), then4(1 * 4 * 1 = 4), for 42. Saving the large values for last keeps them available as multipliers.
Example 3
- Input:
- nums = [7]
- Output:
- 7
- Explanation
- A lone balloon has no neighbours, so both sides count as 1 and it earns 1 * 7 * 1 = 7.
Constraints
- 1 ≤
nums.length≤ 300 - 0 ≤
nums[i]≤ 100