PreviousNext
Coding/Dynamic programming

Burst balloons

Write codeHard35 minGoogle style

Your task

Given positive integer balloon values, you burst them one by one. Bursting balloon i earns left * value[i] * right coins, where left and right are the values of the adjacent surviving balloons (treat out-of-range neighbors as 1). After bursting, neighbors become adjacent. Return the maximum coins from bursting all balloons. The list has at least one balloon.

Examples

burst_balloons(nums: list[int]) -> int
Example 1
Inputburst_balloons([3, 1, 5, 8])
Output167