ALG-H017HardInterval DP
Maximum Balloon Burst Score
Burst balloons in any order. When balloon i bursts, score the product of its current immediate left neighbor, its own value, and its current immediate right neighbor. Missing neighbors count as 1. Return the maximum total score.
Contract
input numbers: integer[]
return integer
Constraints
- • 0 <= length <= 150
- • Every value >= 0
Examples
Example 1
numbers = [3, 1, 5, 8]
→ 167
Example 2
numbers = [1, 5]
→ 10
5 judge tests (2 shown above). Target complexity: O(n^3).