Skip to main content
Back to ChallengesBurst BalloonsHard 40 min

Burst Balloons

You are given n balloons, indexed from 0 to n - 1. If you burst balloon i, you get nums[i - 1] * nums[i] * nums[i + 1] coins. Out of bounds items are treated as 1. Return the maximum coins you can collect by bursting all balloons.

Examples

Input: nums = [3,1,5,8]
Output: 167
Coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167.

Constraints

  • • 1 <= nums.length <= 300
  • • 0 <= nums[i] <= 100

Complexity Analysis

Time
O(n^3)
where n is the number of balloons.
Space
O(n^2)
matrix storing maximum coins for segments.

Test Cases

#1 Standard balloons list
Input: [3,1,5,8]
Expected: 167
#2 Two balloons
Input: [1,5]
Expected: 10
JavaScript
Output
Click "Run Code" to see output here...