hardDynamic Programming 2DPure DSA~45 min
Maximize Coins From Bursting Ad Slots
A row of ad slots each carries a value. Bursting (selling) a slot earns its value times the values of its immediate surviving neighbours. Slots at the ends treat a missing neighbour as 1. Choose a burst order to maximize total coins.
Problem
Given an array nums of n balloons, bursting balloon i earns nums[left] * nums[i] * nums[right] coins where left and right are the adjacent un-burst balloons (treat out-of-bounds as 1). Return the maximum coins obtainable by bursting all balloons.
Input
An integer array nums.
Output
An integer — the maximum total coins.
Constraints
- 1 ≤ n ≤ 300
- 0 ≤ nums[i] ≤ 100
Examples
Example 1
Input
[3,1,5,8]
Output
167
Burst order 1,5,3,8 yields 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167.
Example 2
Input
[1,5]
Output
10
Burst 1 first (1*1*5=5) then 5 (1*5*1=5) → 10.