Skip to content
Get started

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)+
  1. Choosing the first balloon to burst leaves dependent subproblems. What about the last?
  2. If kk is the last balloon between boundaries ii and jj, its neighbours at that moment are exactly ii and jj.
  3. Pad with 1s at both ends and fill F(i,j)F(i,j) by increasing interval length.

Answer

Reveal answer →

129

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading

Related questions