hardDynamic Programming 2DPure DSA~45 min
Maximize Ad Burst Revenue
A row of ad slots each carry a value. Clearing a slot earns the product of its value and its two current neighbours, then the row closes up. Choose the clearing order that maximises total revenue.
Problem
Given n balloons (ad slots) with values in nums, bursting balloon i earns nums[left]·nums[i]·nums[right], where left/right are the adjacent balloons at that moment (out-of-range neighbours count as 1). Return the maximum coins obtainable by bursting all balloons.
Input
An array nums of n values (0 ≤ n ≤ 300), 0 ≤ nums[i] ≤ 100.
Output
An integer — the maximum total coins.
Constraints
- Virtual boundary balloons of value 1 pad both ends
- 0 ≤ n ≤ 300
- Think about which balloon is burst LAST in a range
Examples
Example 1
Input
nums = [3,1,5,8]
Output
167
Optimal order yields 3·1·5 + 3·5·8 + 1·3·8 + 1·8·1 = 167.
Example 2
Input
nums = [1,5]
Output
10
Burst 1 first (1·1·5=5) then 5 (1·5·1=5) → 10.