FunctionRacerProblemsRace

Loot Around the Lantern Ring

MediumDynamic programmingPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems