Tap here to switch tabs
Problem
Submissions

Problem: Burst Balloons

Burst Balloons gives an array of balloon values. Remove every balloon in an order that maximizes coins earned from its current neighbors, treating positions beyond the ends as virtual balloons valued at one.

Statement

You are given nn balloons, numbered from 00 to n−1n - 1. Each balloon has a number painted on it, represented by an integer array nums.

When you burst a balloon ii, you earn coins equal to nums[i - 1] * nums[i] * nums[i + 1].
If either i−1i - 1 or i+1i + 1 is out of bounds, assume there is a virtual balloon with the number 11 in its place.

Your task is to burst all the balloons to collect the maximum number of coins possible.

Return the maximum coins you can obtain by bursting the balloons in an optimal order.

Constraints:

  • n==n == nums.length

  • 1≤n≤1 \leq n \leq 300

  • 0≤0 \leq nums[i] ≤100\leq 100

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Burst Balloons

Burst Balloons gives an array of balloon values. Remove every balloon in an order that maximizes coins earned from its current neighbors, treating positions beyond the ends as virtual balloons valued at one.

Statement

You are given nn balloons, numbered from 00 to n−1n - 1. Each balloon has a number painted on it, represented by an integer array nums.

When you burst a balloon ii, you earn coins equal to nums[i - 1] * nums[i] * nums[i + 1].
If either i−1i - 1 or i+1i + 1 is out of bounds, assume there is a virtual balloon with the number 11 in its place.

Your task is to burst all the balloons to collect the maximum number of coins possible.

Return the maximum coins you can obtain by bursting the balloons in an optimal order.

Constraints:

  • n==n == nums.length

  • 1≤n≤1 \leq n \leq 300

  • 0≤0 \leq nums[i] ≤100\leq 100