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, j-1), 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 j-i 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, j-1); 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, j-1); 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.