Skip to content
BASA DSA

Burst Balloons

Hard2-D Dynamic Programming

Burst all balloons in some order. Bursting a balloon earns its value times its current left and right neighbors; a missing neighbor has value one. Return the greatest possible total.

Example 1

Input
nums = [3,1,5,8]
Output
167

Explanation

Burst original 1 for 15, then 5 for 120, then 3 for 24, then 8 for 8, totaling 167.

Example 2

Input
nums = [2,4]
Output
12

Explanation

Burst 2 for 8 then 4 for 4, totaling 12 rather than the reverse order's 10.

Example 3

Input
nums = []
Output
0

Explanation

No balloons earn no coins.

Constraints

  • 0 <= len(nums) <= 300
  • Values are 0..100

Function contractmaxCoinsArguments: json
Loading draft…
SolutionRuns on your device