Math Dynamic Programming
Guru Level

Implement the burstBalloonsMaxCoins method that returns the maximum coins obtainable by bursting balloons in the best order.

You are given an array where each value represents a balloon. When a balloon at position i is burst, the coins gained are the product of the nearest remaining value on the left, the current value, and the nearest remaining value on the right.

Assume there is a virtual balloon with value 1 outside both ends of the array. Return the maximum coins possible by choosing the best bursting order.

Example 1
Input:
nums (int[]) = [3,1,5,8]
size (int) = 4
Return:
(int) 167
Example 2
Input:
nums (int[]) = [1,5]
size (int) = 2
Return:
(int) 10
Example 3
Input:
nums (int[]) = [7]
size (int) = 1
Return:
(int) 7

The difficult part is that bursting one balloon changes its neighbors. Instead of thinking about the first balloon to burst, think about the last balloon burst inside an interval.

If a balloon is the last one burst between two boundaries, its left and right neighbors are fixed. Use interval dynamic programming where dp[left][right] stores the maximum coins from bursting balloons strictly between left and right.

Try every balloon as the last balloon in each interval and keep the best result.

Pseudocode:

function burstBalloonsMaxCoins(nums, size):
    values = [1] + nums + [1]
    create dp table filled with 0
    for length from 2 to size + 1:
        for left from 0 to size + 1 - length:
            right = left + length
            for last from left + 1 to right - 1:
                coins = values[left] * values[last] * values[right]
                coins += dp[left][last] + dp[last][right]
                dp[left][right] = max(dp[left][right], coins)
    return dp[0][size + 1]
Run your code to see the result.