Festival Game | Bursting Balloons

Problem Statement

You have a row of targets, each with a point value. When you hit target i, you score target[i-1] × target[i] × target[i+1] points (the product of the target and its neighbors). After hitting a target, it disappears and the remaining targets close the gap. Edge targets treat missing neighbors as value 1.

targets = [3, 1, 5, 8]

One possible sequence:
Hit 1: score = 3×1×5 = 15, remaining = [3, 5, 8]
Hit 5: score = 3×5×8 = 120, remaining = [3, 8]
Hit 3: score = 1×3×8 = 24, remaining = [8]
Hit 8: score = 1×8×1 = 8, remaining = []

Total = 15 + 120 + 24 + 8 = 167

Find the maximum possible total score.