Loot Around the Lantern Ring
coins[i] is the number of coins hanging in lantern i of a ring of lanterns. You may take the coins from any lanterns you choose, except that no two chosen lanterns may be neighbors in the ring. Lanterns i and i + 1 are neighbors, and so are the last lantern and lantern 0, because the ring closes. Return the most coins you can take. With a single lantern, simply take it. Taking nothing is allowed and gives 0.
Example 1
coins [4,1,2,7,5]
returns 11
Lanterns 0 and 3 are not neighbors, so you can take 4 + 7 = 11; any three lanterns would include two neighbors.
Example 2
coins [8,2,8]
returns 8
Lanterns 0 and 2 are neighbors because the ring closes, so you can take only one of the 8s.
Constraints
1 <= len(coins) <= 500 <= coins[i] <= 100
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Lowest Photo WallMedium
- Lucky Toll TripsMedium
- No Double LeapsMedium
- One Forgiven DayMedium
- Paint the FenceMedium
- Shared Subsequence LengthMedium
- Trading With Rest DaysMedium
- Unique Binary Search TreesMedium