Given an array nums of balloons, each with a positive value, return the maximum number of coins you can collect by bursting the balloons in the best order. Pattern focus: Interval DP. Consider which balloon is burst last in each interval so the remaining boundaries are already fixed.
nums = array of positive integers
maximum coins obtainable
Example 1:
Input:
nums = [3,1,5,8]
Output:
167
Explanation:
This is the classic standard example.
Example 2:
Input:
nums = [1,5]
Output:
10
Explanation:
Bursting 1 first and 5 last gives the best total.
Example 3:
Input:
nums = [7]
Output:
7
Explanation:
A single balloon yields 1 × 7 × 1 = 7 coins.