The last one standing, not the first one gone
Instead of picking which balloon bursts first, pick which one bursts last within a range. About 15 minutes.
Bursting changes the neighbours
Balloons stand in a row, each with a number. Burst one and you earn its number times its left neighbour's times its right neighbour's. Then it's gone, and its two neighbours are now next to each other. The order you burst them in changes the total.
Asking "which balloon goes first?" gets messy: after it bursts, the two sides touch and affect each other.
Ask which balloon goes last
Flip the question. In any stretch, which balloon bursts last? By then everything else in the stretch is gone, so its neighbours are the two balloons just outside the stretch. They're known, fixed and untouched. And the two sides were burst separately, without affecting each other.
Put a 1 at each end so every balloon has neighbours. Then try each balloon as the last in its stretch: its own coins plus the best for each side. For 3, 1, 5, 8 the best total is 167.
last = nums[i] * nums[k] * nums[j]
One balloon between i and j: it bursts last and earns left × it × right. Between the padding 1 and the 4: 1 × 2 × 4 = 8. Around the 4: 2 × 4 × 3 = 24. Around the 3: 4 × 3 × 1 = 12.
Only one balloon is left between two others. It shows 5, and its neighbours show 3 and 7. How many coins does bursting it earn?
- A105
- B15
- C35
Show the answer
105. 3 × 5 × 7 = 105. Nothing else is left in between, so that's all of it.
Burst balloons for maximum coins
You get nums, the values of n balloons in a row. Bursting a balloon earns left × value × right coins, where left and right are the values of its current neighbours (1 if it's at either end with nothing there). Bursting it removes it, so its former neighbours become neighbours of each other. Return the maximum total coins from bursting every balloon, in some order.
nums = [3, 1, 5, 8] → 167
0 ≤ n ≤ 300 · 0 ≤ nums[i] ≤ 100 · return a long