Arena Relic Draft Duel
Optimal score difference as players take 1–2 values from either array end
An online game's duel mode places a row of relics between two players. Each relic has a signed point value: valuable relics add points, while cursed relics subtract points.
You take the first turn. On each turn, the current player must choose one of these actions:
- Take the leftmost relic.
- Take the rightmost relic.
- If at least two relics remain, take the two leftmost relics together.
- If at least two relics remain, take the two rightmost relics together.
The chosen relics are removed, and their values are added to that player's score. Taking two relics means taking both from the same end, not one from each end. Neither player may skip a turn. The duel ends when the row is empty.
Both players play optimally to maximize their own final score minus the other player's final score.
Given the relic values in left-to-right order, return your final score minus your opponent's final score under optimal play. A negative result means your opponent wins. An empty row has a result of zero.
Examples
Example 1
Input: relics = [8,1,3] Output: 6
Taking the two leftmost relics together gives you the relics valued 8 and 1, leaving only the relic valued 3 for your opponent. This is better than any other opening move.
Example 2
Input: relics = [-5,-2] Output: 3
Both relics are cursed, but turns cannot be skipped. Taking only the rightmost relic leaves the more costly curse for your opponent.
Example 3
Input: relics = [] Output: 0
There are no relics, so neither player takes a turn or earns points.
Constraints
- 0 <= len(relics) <= 1200
- -1000000 <= relics[i] <= 1000000
- Every relic value is an integer.
The intended solution uses interval dynamic programming in O(n^2) time. Since transitions use only intervals shorter by one or two relics, storing two previous interval-length layers reduces auxiliary space to O(n). All possible score differences fit exactly in JavaScript's Number type under these constraints.
Hints
Show hint 1Hint 1
Define a state for a remaining interval from the perspective of the player whose turn it is.
Show hint 2Hint 2
After taking relics worth s points, the opponent becomes the current player on the remaining interval. How should that interval's optimal score difference affect your result?
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you reconstruct one optimal sequence of moves, breaking ties in the order left-one, right-one, left-two, right-two?
- How would the recurrence and complexity change if a player could take any number from 1 through k from a single end?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem