Full lesson preview

Find the maximum coins from burst balloons

Given balloons with numbers, determine the maximum coins obtainable by choosing the order to burst them.

Python practice30 minDynamic ProgrammingAdvancedLast updated March 29, 2026

Problem statement

You are given an array of positive integers nums representing balloons. When you burst balloon i, you gain coins equal to nums[left] * nums[i] * nums[right], where left and right are the adjacent remaining balloons to the left and right of i. If there is no such balloon, treat it as having value 1 (virtual boundary). After bursting balloon i, it is removed and the left and right become adjacent. Return the maximum number of coins you can collect by bursting the balloons in an optimal order. This is the classic 'Burst Balloons' dynamic programming problem. The optimal solution pads the array with 1 at both ends and computes the best substructure using DP — considering which balloon is the last to burst in each interval.

Task

Implement a dynamic programming solution (tabulation or memoization) to compute the maximum coins you can collect by bursting balloons optimally.

Examples

Classic example

Input

[3, 1, 5, 8]

Output

167

Burst balloons in order 1, 5, 3, 8 (or other optimal order) to collect total 167 coins.

Input format

A single function call max_coins(nums) where nums is a list of positive integers.

Output format

Return an integer representing the maximum coins collectible.

Constraints

0 <= len(nums) <= 100; 1 <= nums[i] <= 1000. Aim for O(n^3) time and O(n^2) space solution.

Samples

Sample 1

Input

[1, 5]

Output

Burst 1 then 5: coins = 1*1*5 + 1*5*1 = 5 + 5 = 10.