Back to DSA
Burst Balloons
hardAn array of positive integers represents a line of items, each labeled with a score. When you remove item i, you earn score[i-1] score[i] score[i+1] points. Boundary items that are out of range count as having a score of 1. Determine the maximum total points achievable by removing all items.
Examples
Example 1:
Input:
nums = [2,4,3,5]Output:
110Explanation: An optimal removal order yields the maximum of 110 points.
Example 2:
Input:
nums = [1,5]Output:
10Explanation: Remove 1 first (1*1*5=5), then 5 (1*5*1=5). Total = 10.
Hints
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[] arr = new int[n + 2];
arr[0] = arr[n + 1] = 1;
for (int i = 0; i < n; i++) arr[i + 1] = nums[i];
int[][] dp = new int[n + 2][n + 2];
for (int len = 1; len <= n; len++) {
for (int left = 1; left <= n - len + 1; left++) {
int right = left + len - 1;
for (int k = left; k <= right; k++) {
dp[left][right] = Math.max(dp[left][right],
dp[left][k - 1] + arr[left - 1] * arr[k] * arr[right + 1] + dp[k + 1][right]);
}
}
}
return dp[1][n];
}
}Time complexity
O(n^3)Space complexity
O(n^2)