Pop Lanterns for the Most Coins
A row of paper lanterns has values lanterns[i]. You pop them one at a time, in any order you like. Popping lantern i earns left * lanterns[i] * right coins, where left and right are the values of its nearest lanterns still hanging on each side; a missing neighbour counts as 1. After popping, the two neighbours become adjacent.
Return the most coins you can earn by popping every lantern.
Example 1
Input: lanterns = [3,1,5,8] Output: 167 Explanation: Pop 1, 5, 3, 8: 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15 + 120 + 24 + 8 = 167.
Example 2
Input: lanterns = [2,4,3] Output: 33
Constraints
- 0 <= lanterns.length <= 300
- 0 <= lanterns[i] <= 100
Hint 1
Think about which lantern is popped last inside a range: its neighbours at that moment are the range borders.
Hint 2
Let best[lo][hi] be the most coins from popping everything strictly between lo and hi; try every k as the last one popped.
Discussion 0
Join free to post in the discussion.
Good practice for: Game Developer, Backend Developer, Data Scientist, Machine Learning Engineer, Automation Test Engineer
Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.