Burst Balloons

Difficulty: Hard

You have a row of balloons, each with a number painted on it. Bursting a balloon earns you coins equal to the product of the numbers on its current left neighbor, itself, and its current right neighbor — "current" meaning at the moment you burst it, after any other balloons around it have already been burst and removed. If a burst balloon has no neighbor on one side (because it's at the edge of the row, or its neighbor is already gone), treat that missing side as a 1.

Burst every balloon, in whatever order you choose, to maximize the total coins collected.

Examples

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

Bursting in the order 1, 5, 3, 8 earns 315 + 358 + 138 + 181 = 15 + 120 + 24 + 8 = 167.

Input: nums = [1,5]
Output: 10

Burst either balloon first: 115 + 151, or 151 + 111 — the best ordering gives 10.

Constraints

  • 1 <= nums.length <= 300

  • 0 <= nums[i] <= 100

Approach

Thinking about which balloon to burst first is awkward, because bursting it changes who's adjacent to everything else. Instead, think about which balloon in a range is burst last.

Pad the row with a 1 balloon at each end (so every real balloon always has a neighbor to multiply against). Define dp[left][right] as the most coins obtainable from bursting every balloon strictly between positions left and right (both of which stay un-burst, acting as fixed boundary markers).

If balloon k (somewhere strictly between left and right) is the last one burst in that range, then at the moment it bursts, everything else in the range is already gone — so its neighbors are exactly left and right themselves. That gives: nums[left] * nums[k] * nums[right] + dp[left][k] + dp[k][right], where the two dp terms cover bursting everything on either side of k (which happened before k, in some order that doesn't matter). Try every possible k and keep the best.

Fill the table by increasing range width, since wider ranges depend on narrower ones. The final answer is dp[0][n+1] across the padded array (or equivalently, the range spanning every real balloon).

Solutions

Brute Force — Recursion Over Bursting Order

Directly simulate the problem: at each step, try bursting each remaining balloon next (using its actual current neighbors), remove it, and recurse on what's left. This explores every possible bursting order.

function maxCoins(nums) {
  function solve(balloons) {
    if (balloons.length === 0) return 0;

    let best = 0;
    for (let i = 0; i < balloons.length; i++) {
      const left = i > 0 ? balloons[i - 1] : 1;
      const right = i < balloons.length - 1 ? balloons[i + 1] : 1;
      const gained = left * balloons[i] * right;

      const remaining = balloons.slice(0, i).concat(balloons.slice(i + 1));
      best = Math.max(best, gained + solve(remaining));
    }
    return best;
  }

  return solve(nums);
}

Time: O(n!) in the worst case — every possible bursting order is tried · Space: O(n^2) — each recursive call copies a shorter array

Optimal — Interval DP: Which Balloon Bursts Last?

Pad the array with 1s at both ends, then build a table over (left boundary, right boundary) by increasing range width, trying every choice of 'last balloon burst' within each range.

function maxCoins(nums) {
  const balloons = [1, ...nums, 1];
  const n = balloons.length;
  const table = Array.from({ length: n }, () => new Array(n).fill(0));

  for (let length = 2; length < n; length++) {
    for (let left = 0; left + length < n; left++) {
      const right = left + length;
      for (let k = left + 1; k < right; k++) {
        const coins = balloons[left] * balloons[k] * balloons[right] + table[left][k] + table[k][right];
        table[left][right] = Math.max(table[left][right], coins);
      }
    }
  }

  return table[0][n - 1];
}

Time: O(n^3) · Space: O(n^2)