Burst Balloons: the idea to remember.

The core insight

Choose the final balloon burst inside each interval, keeping the interval's two boundaries fixed.

Why it works

Once the last balloon is chosen, the left and right intervals become independent and their rewards can be added.

The mistake to avoid

Choose the last balloon, not the first, so outside neighbors remain well defined. Pad the array with ones.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Choose the final balloon burst inside each interval, keeping the interval's two boundaries fixed.
public int maxCoins(int[] nums) {
    var dp = new int[nums.length][nums.length];

    return burst(nums, 0, nums.length - 1, dp);
}

private int burst(int[] nums, int left, int right, int[][] dp) {
    if (left > right) {
        return 0;
    }
    if (dp[left][right] != 0) {
        return dp[left][right];
    }

    for (int i = left; i <= right; i++) {
        int coins = nums[i];

        if (left - 1 >= 0) {
            coins *= nums[left - 1];
        }
        if (right + 1 < nums.length) {
            coins *= nums[right + 1];
        }

        coins +=
            burst(nums, left, i - 1, dp) + burst(nums, i + 1, right, dp);
        dp[left][right] = Math.max(dp[left][right], coins);
    }

    return dp[left][right];
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection