You are given nums, the numbers painted on a row of balloons. Bursting the balloon at index i earns you left * nums[i] * right coins, where left and right are the balloons immediately beside it at that moment. A missing neighbour (off the end of the row) counts as a balloon painted 1. After a burst the row closes up. Return the most coins you can collect by bursting all of them.
- You choose the order freely
- An empty row earns
0 - Greedily bursting the cheapest (or the most expensive) balloon first is not optimal