Burst Balloons
Hard · Dynamic Programming · about 35 minutes
Balloons stand in a row, balloon i carrying the number nums[i]. Popping a balloon pays the product of its number and the numbers of the balloons currently on its left and right (a missing neighbor counts as 1), and then those two neighbors become adjacent. Pop every balloon in the order of your choosing and return the highest total payout.