Pop the Lanterns
Problem
A festival row holds paper lanterns with brightness values vals. You pop them one at a time. Popping a lantern earns left · own · right coins, where left and right are the brightness of its current neighbours still hanging in the row; a missing neighbour (past either end) counts as 1.
After a pop, its neighbours become adjacent. Return the maximum number of coins you can earn by popping every lantern.
Example 1
- Input:
- vals = [4, 1, 6, 2]
- Output:
- 84
Pop 1 (4·1·6 = 24), then 6 (4·6·2 = 48), then 2 (4·2·1 = 8), then 4 (1·4·1 = 4): 24 + 48 + 8 + 4 = 84.
Example 2
- Input:
- vals = [5, 2]
- Output:
- 15
Pop 2 first (5·2·1 = 10), then 5 (1·5·1 = 5).
Constraints
- 0 ≤ vals.length ≤ 300
- 0 ≤ vals[i] ≤ 100
Hint
Show the first hint
Choosing the first lantern to pop leaves two halves that still interact through their new neighbours. Try a different viewpoint.
Walkthrough
How to approach it
01Clarify before coding
- Do neighbours mean the current ones, not the original ones? Yes, popped lanterns disappear.
- Can brightness be 0? Yes; such lanterns still have to be popped.
- Can the row be empty? Yes, the answer is 0.
02Brute force
Try every popping order (all n! permutations) and simulate the coins.
Cost: O(n! · n): hopeless beyond about 10 lanterns.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.