Burst the balloons for the most coins
Balloons in a row carry numbers [2, 4, 1, 6, 3]. Bursting a balloon earns (its number) × (its current left neighbour) × (its current right neighbour), where a missing neighbour counts as 1; the burst balloon then disappears and its neighbours become adjacent. You burst all five in an order of your choice. What is the maximum total earned?
Show hints (3)+
- Choosing the first balloon to burst leaves dependent subproblems. What about the last?
- If is the last balloon between boundaries and , its neighbours at that moment are exactly and .
- Pad with 1s at both ends and fill by increasing interval length.
Answer
Reveal answer →Final answer
129
Create a free account to see the full worked solution and track your progress.
Interview format: Prop Trading