DDSA Solutions

1872. Stone Game VIII

HardView on LeetCode
ArrayMathDynamic ProgrammingPrefix SumGame Theory

Problem Overview

Each move replaces stones[0..i] with their sum, so the new first stone is prefix[i] and the opponent faces the leftover suffix.

Intuition

Each move replaces stones[0..i] with their sum, so the new first stone is prefix[i] and the opponent faces the leftover suffix. The score you just scored is prefix[i], then the opponent plays optimally on that suffix. That gives dp[i] = max over later starts j of prefix[j] - dp[j]. Walking from the right, only the next dp value is live, so one variable is enough. Alice must take at least two stones, so the last start index is 1.

Algorithm

  1. 1Overwrite stones[i] with the prefix sum through i.
  2. 2Set ans = stones[n-1] (take the whole prefix as the last remaining move).
  3. 3For i from n-2 down to 1: ans = max(ans, stones[i] - ans).
  4. 4Return ans. This is Alice minus Bob under optimal play.

Example Walkthrough

Input: stones = [-1, 2, -3, 4, -5]

  1. 1.Prefixes: [-1, 1, -2, 2, -3].
  2. 2.Start with ans = -3 (take everything).
  3. 3.i = 3: max(-3, 2 - (-3)) = 5.
  4. 4.i = 2: max(5, -2 - 5) = 5.
  5. 5.i = 1: max(5, 1 - 5) = 5.

Output: 5

Common Pitfalls

  • •The first take must cover at least two stones, so do not consider i = 0 as a start.
  • •Score is prefix of the take, not the sum of remaining stones.
  • •The recurrence uses the opponent's best from the next state, so a left-to-right pass needs a full array; right-to-left folds it.
  • •Mutating stones stores prefixes in place. A copy is only needed if the caller forbids writes.
1872.cs
C#
// Approach: After a take of stones[0..i], the pile becomes prefix[i] plus the
// unused suffix, so the opponent starts at i. Current best difference is
// max(skip to a later start, prefix[i] - opponentBest). Walk right to left;
// only the next dp value is needed, so keep one variable.
// Complexity: O(n) time and O(1) extra space (prefix written into stones).
public class Solution
{
    public int StoneGameVIII(int[] stones)
    {
        int n = stones.Length;
        for (int i = 1; i < n; i++)
            stones[i] += stones[i - 1];

        int ans = stones[n - 1];
        for (int i = n - 2; i >= 1; i--)
            ans = Math.Max(ans, stones[i] - ans);

        return ans;
    }
}
Was this solution helpful?

Related Problems