Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Dynamic Programming

Burst Balloons

Hard · Dynamic Programming · Asked at Google, Amazon, Microsoft, Snapchat

Bursting balloon i earns left · a[i] · right, where left and right are the values of its current neighbours (a missing neighbour counts as 1); the burst balloon then disappears. Burst all balloons and print the maximum total coins.

Input

First line: n. Second line: n space-separated integers.

Output

The maximum coins.

Constraints

Think about the LAST balloon k burst inside an open interval (i, j): its neighbours are then i and j. best(i, j) = max over k of best(i, k) + best(k, j) + v[i]·v[k]·v[j], with 1s padded at both ends.

Example 1

Input

4
3 1 5 8

Output

167

Example 2

Input

2
1 5

Output

10

Hints

  1. Choosing the first balloon to burst makes the subproblems depend on each other. Instead choose the LAST balloon to burst in a range.
  2. Pad the array with 1 at both ends. If k is the last balloon burst strictly between i and j, it earns v[i]·v[k]·v[j], and the two sides (i, k) and (k, j) are independent.

Approach

dp[i][j] = maximum coins from bursting every balloon strictly between i and j (padded indices). For increasing gap lengths, dp[i][j] = max over k in (i, j) of dp[i][k] + dp[k][j] + v[i]·v[k]·v[j]: when k goes last, its neighbours are exactly the boundaries i and j. The answer is dp[0][n+1].

Complexity: O(n³) time · O(n²) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> v(n + 2, 1);
    for (int i = 1; i <= n; i++) cin >> v[i];
    int N = n + 2;
    vector<vector<long long>> dp(N, vector<long long>(N, 0));
    for (int len = 2; len < N; len++)
        for (int i = 0; i + len < N; i++) {
            int j = i + len;
            for (int k = i + 1; k < j; k++) dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + v[i] * v[k] * v[j]);
        }
    cout << dp[0][N - 1] << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
v = [1] + data[1 : 1 + data[0]] + [1]
N = len(v)
dp = [[0] * N for _ in range(N)]
for length in range(2, N):
    for i in range(N - length):
        j = i + length
        vij = v[i] * v[j]
        row_i = dp[i]
        best = 0
        for k in range(i + 1, j):
            cand = row_i[k] + dp[k][j] + vij * v[k]
            if cand > best:
                best = cand
        row_i[j] = best
print(dp[0][N - 1])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] v = new long[n + 2];
        v[0] = v[n + 1] = 1;
        for (int i = 1; i <= n; i++) v[i] = sc.nextLong();
        int N = n + 2;
        long[][] dp = new long[N][N];
        for (int len = 2; len < N; len++)
            for (int i = 0; i + len < N; i++) {
                int j = i + len;
                for (int k = i + 1; k < j; k++) dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + v[i] * v[k] * v[j]);
            }
        System.out.println(dp[0][N - 1]);
    }
}

Solve Burst Balloons online · All practice problems