Solution
Approach 1: Dynamic Programming
Intuition
Let's change the game so that whenever Lee scores points, it deducts from Alex's score instead.
Let dp(i, j)
be the largest score Alex can achieve where the piles remaining are piles[i], piles[i+1], ..., piles[j]
. This is natural in games with scoring: we want to know what the value of each position of the game is.
We can formulate a recursion for dp(i, j)
in terms of dp(i+1, j)
and dp(i, j1)
, and we can use dynamic programming to not repeat work in this recursion. (This approach can output the correct answer, because the states form a DAG (directed acyclic graph).)
Algorithm
When the piles remaining are piles[i], piles[i+1], ..., piles[j]
, the player who's turn it is has at most 2 moves.
The person who's turn it is can be found by comparing ji
to N
modulo 2.
If the player is Alex, then she either takes piles[i]
or piles[j]
, increasing her score by that amount. Afterwards, the total score is either piles[i] + dp(i+1, j)
, or piles[j] + dp(i, j1)
; and we want the maximum possible score.
If the player is Lee, then he either takes piles[i]
or piles[j]
, decreasing Alex's score by that amount. Afterwards, the total score is either piles[i] + dp(i+1, j)
, or piles[j] + dp(i, j1)
; and we want the minimum possible score.
Complexity Analysis

Time Complexity: , where is the number of piles.

Space Complexity: , the space used storing the intermediate results of each subgame.
Approach 2: Mathematical
Intuition and Algorithm
Alex clearly always wins the 2 pile game. With some effort, we can see that she always wins the 4 pile game.
If Alex takes the first pile initially, she can always take the third pile. If she takes the fourth pile initially, she can always take the second pile. At least one of first + third, second + fourth
is larger, so she can always win.
We can extend this idea to N
piles. Say the first, third, fifth, seventh, etc. piles are white, and the second, fourth, sixth, eighth, etc. piles are black. Alex can always take either all white piles or all black piles, and one of the colors must have a sum number of stones larger than the other color.
Hence, Alex always wins the game.
Complexity Analysis
 Time and Space Complexity: .
Analysis written by: @awice.