Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

182. Burst Balloons

HardDay 54 of 60Dynamic Programming

There are n balloons in a row, balloon i showing the number nums[i]. Bursting balloon i earns nums[left] * nums[i] * nums[right] coins, where left and right are its current neighbours; a missing neighbour counts as 1. After a burst, its neighbours become adjacent. Return the maximum coins you can collect by bursting all balloons.

Example 1
Input: nums = [3,1,5,8]
Output: 167
Burst 1, 5, 3, 8 in that order: 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167.
Example 2
Input: nums = [1,5]
Output: 10
Constraints
  • 1 <= nums.length <= 300
  • 0 <= nums[i] <= 100
Hints
Frequently asked at: Google, Amazon, Microsoft
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min