Burst Balloons

Balloons in a row have numbers a[0] … a[n−1]. Bursting balloon i earns left × a[i] × right coins, where left and right are the numbers of its current neighbours (after earlier bursts); a missing neighbour counts as 1. Burst all balloons in the best order. What is the maximum total?

Input:

• line 1: n
• line 2: n integers

Output: the maximum number of coins.

Constraints: 1 ≤ n ≤ 200, 0 ≤ a[i] ≤ 100.

The key insight: don't think about which balloon to burst first — think about which balloon in an interval (l, r) is burst last. Then its neighbours are exactly a[l] and a[r], and the two sides are independent: dp[l][r] = max over k of dp[l][k] + dp[k][r] + a[l]·a[k]·a[r] (with 1s padded at both ends). O(n³) interval DP.