Problem statement

https://leetcode.com/problems/stone-game-viii/

Solution

Let us look at numbers a, b, c, d, e, then on the next step we can have for example a + b + c, d, e and then a + b + c + d + e. Note, that on each step what we are actually have is some prefix sum as the first element. So, the problem can be reformulated in the following way: given some prefix sums a + b, a + b + c, a + b + c + d, a + b + c + d + e we have two players which play the following game: once number is taken, other player can take only the number to the right of this number.

Let us now use the idea of dynamic programming: let say dp[i] be the maximum gain we can have if we take number with index i and then we play optimally. However in this case we will have O(n^2) complexity, which is too big for this problem. Instead we start from the last element and go in the opposite direction. Imagine, that w have -1, 2, -3, 4, -5, then we work with prefix sums 1, -2, 2, -3.

  1. On the first step we have -3, that is we have answer -3 for the last element, we do not have choice.
  2. On the second step we have new number 2, and we need to look at the biggest among ans, num - ans number. Why though. By definition we are trying to find the best gain we can have if we take number 2. So, what is the strategy for the opposite player? To choose the bigest possible gain.
  3. We have 5 still.
  4. We have 5 still.

More explanations. Why it is optimal to take ans = max(ans, num - ans) on the each step? What we keep in ans is the maximum gain we can have if we start somewhere in the [i, end] range. Then how we can calculate value for i-1? We can either take this number, then we gain its value num, but we understand that other player will play optimally and gain ans, so we have difference num - ans in this case. Or we can not take this element, then we do not change our turn and we can gain ans.

Complexity

Time complexity is O(n), space complexity is O(1)

Code

class Solution:
    def stoneGameVIII(self, stones):
        ans = sum(stones)
        for num in list(accumulate(stones))[::-1][1:-1]:
            ans = max(ans, num - ans)
        return ans

Oneliner

return reduce(lambda m, c : max(m, c - m), list(accumulate(stones))[::-1][:-1])