DSAhardArrays~40m

Pop Star

Problem

You are playing an arcade balloon-popping game. Each balloon has a number printed on it. When you pop balloon i, you score points equal to the product of balloon i and its nearest remaining neighbors on the left and right. If no neighbor exists on a side, treat it as 1.

After popping all balloons, return your maximum possible total score.

The key insight: thinking about which balloon to pop FIRST leads to an exponential search. Think instead about which balloon to pop LAST in any given range — this leads to an O(n³) interval DP solution.

Examples

Example 1

Input: [1, 5, 1]

Output: 15

Greedy (pop 5 first): 1×5×1 + 1 + 1 = 7. Optimal: pop left 1 (score 5), pop right 1 (score 5), pop 5 (score 5). Total = 15. Save the largest for last.

Example 2

Input: [3, 1, 5, 8]

Output: 167

Optimal order: pop 1 (3×1×5=15), pop 5 (3×5×8=120), pop 3 (1×3×8=24), pop 8 (1×8×1=8). Total=167. Counterintuitive — neither greedy nor obvious.

Example 3

Input: [2, 3, 2]

Output: 18

Pop middle 3 first: 2×3×2=12. Then pop either 2: 1×2×2=4. Then last 2: 1×2×1=2. Total=18. Popping smallest first gives only 15.

Constraints

›1 <= n <= 300
›1 <= nums[i] <= 100

Loading question…