A row of n relic tokens is laid out, each stamped with a positive integer value. Two collectors alternate turns, with the first collector going first. On a turn, a collector removes the token at either the far-left or far-right end of the current row and adds its value to their own hoard. Both play perfectly: each move is chosen to maximize the final value of that collector's own hoard, knowing the opponent does the same.
Report the margin of the first collector: the total value of the first collector's hoard minus the total value of the second collector's hoard, under optimal play by both.
Line 1: an integer n, the number of tokens.
Line 2: n space-separated positive integers, the token values from left to right.
A single integer: (first collector's total) - (second collector's total) under optimal play.
Example 1
Input
4 1 5 2 4
Expected
6
Explanation
With both playing optimally the first collector ends 6 ahead of the second (first collects 9, second collects 3).
Example 2
Input
1 7
Expected
7
Explanation
Only one token exists; the first collector takes it, so the margin is 7 - 0 = 7.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →