Burst balloons
SalesforceThe problem
Given n balloons, indexed from 0 to n - 1, each balloon is painted with a number on it represented by an array nums. Burst all the balloons.
If the ith balloon is burst, the coins obtained are nums[i - 1] * nums[i] * nums[i + 1]. If i - 1 or i + 1 goes out of bounds of the array, treat it as if there is a balloon with a 1 painted on it.
Return the maximum coins that can be collected by bursting the balloons wisely.
Input : nums = [3, 1, 5, 8] Output : 167 Explanation : nums = [3, 1, 5, 8] --> [3, 5, 8] --> [3, 8] --> [8] --> [] coins = 315 + 358 + 138 + 181 = 167.
Input : nums = [1, 2, 3, 4] Output : 40 Explanation : nums = [1, 2, 3, 4] --> [1, 2, 4] --> [1, 4] --> [4] --> [] coins = 234 + 124 + 114 + 141 = 40.
Input : nums = [1, 5]
- 1 <= n <= 300
- 1 <= nums[i] <= 100
cpp
class Solution {
public:
int maxCoins(vector<int>& nums){
//your code goes here
}
};java
class Solution {
public int maxCoins(int[] nums) {
//your code goes here
}
}python
class Solution:
def maxCoins(self, nums):
#your code goes herejavascript
class Solution {
maxCoins(nums) {
//your code goes here
}
}csharp
public class Solution
{
public int MaxCoins(List<int> nums)
{
//your code goes here
}
}go
func maxCoins(nums []int) int {
}Stuck? Show a way to structure it+
- 01Pad nums with sentinel 1 values.
- 02Let dp[left][right] mean maximum coins for the open interval.
- 03Choose each index i as the last balloon burst.
- 04Combine independent left and right intervals.
- 05Fill intervals by increasing length.
Reference answer
Then expect these follow-ups
How would you recover one optimal burst order?
Tests: follow-up reasoning
Why is last-burst reasoning cleaner than first-burst reasoning?
Tests: correctness reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question