Problem statement. The input is an array $A$ of $n$ positive integers representing balloons. If we burst balloon $i$, we receive $A[i-1] \cdot A[i] \cdot A[i+1]$ points, where out-of-bounds values are treated as 1. Burst balloons disappear, so future points are calculated according to whatever remains. Our goal is to return the maximum number of points we can receive by bursting all $n$ balloons. (This is LeetCode 312.)
Solution. Pad $A$ with 1's on both ends, and let $\mathsf{OPT}[i][j]$ be the maximum possible points from bursting all balloons strictly between indices $i$ and $j$.
ALG(A):
A = [1] + A + [1] # indices of A are now 0, ..., n+1
d = 2-D array where d[i][j] = 0
for all i in {0, ..., n} and j in {0, ..., n+1}
for i = n-1, ..., 0:
for j = i+2, ..., n+1:
for k = i+1, ..., j-1:
d[i][j] = max(d[i][j],
A[i]*A[k]*A[j] + d[i][k] + d[k][j])
return d # answer is d[0][n+1]
Correctness (sketch). For all $k \in \{i+1, \ldots, j-1\}$, if we burst balloon $k$ last among these indices, then everything else between $i$ and $j$ has already been popped, so $k$'s neighbors are exactly $A[i]$ and $A[j]$. Thus, we'd receive $A[i] \cdot A[k] \cdot A[j]$ points for bursting $k$. We'd also receive all of the points from bursting $i$ to $k$, and $k$ to $j$ (excluding all endpoints). These last two values are $\mathsf{OPT}[i][k]$ and $\mathsf{OPT}[k][j]$, respectively. Maximizing over all $k$ yields the recurrence used by the algorithm.
What to submit. You'll be given a random instance using the generate function below. You should submit the 2-D array d.
Practice. Enter an array below or click Generate for a random one. Click Solve to check your answer.
import random
def generate():
A = [1, 2, 2, 3, 4]
random.shuffle(A)
return A
def solve(A):
A = [1] + A + [1]
m = len(A)
d = [[0]*m for _ in range(m-1)]
for i in range(m-3, -1, -1):
for j in range(i+2, m):
for k in range(i+1, j):
d[i][j] = max(d[i][j],
A[i]*A[k]*A[j] + d[i][k] + d[k][j])
return d # answer is d[0][m-1]