Choose an order to burst balloons to maximize the total coins gained.
Burst Balloons
You are given an array nums where each element represents a balloon with a positive integer value.
When you burst a balloon at index i, you gain coins equal to the product of the values of its nearest remaining neighbors on the left and right, multiplied by nums[i] itself. If one side has no remaining balloon, treat that missing value as 1.
Your task is to determine the maximum number of coins you can collect by bursting all balloons in an optimal order.
Because the neighbors change after every burst, the order matters.
Notes
- Every balloon must be burst exactly once.
- The array can be considered to have virtual balloons with value
1at both ends. - You want the best possible total, not just a locally good choice.
Input Format
- A list of positive integers
nums. - Each value represents one balloon.
Output Format
- Return a single integer: the maximum coins obtainable by bursting all balloons.
Constraints
1 <= nums.lengthnums[i] > 0- The exact constraints may vary by platform version, but the intended solution should be polynomial-time DP rather than brute force.
Example 1
Input
nums = [3,1,5,8]
Output
167
Explanation
One optimal order is to burst 1, then 5, then 3, then 8. With virtual balloons of value 1 at both ends, the best total is 167.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.