Stone Game VIII

Hard

#1710Time: O(n^2) - Calculating prefix sums takes O(n). The nested loops for the DP calculation take O(n^2) time.Space: O(n) - We use O(n) space for the prefix sum array and O(n) for the dp array.1 company

Patterns

Math Dynamic Programming Prefix Sum Game Theory

Data structures

Array

Companies

Infosys

Prompt

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones arranged in a row. On each player's turn, while the number of stones is more than one, they will do the following:

Choose an integer x > 1, and remove the leftmost x stones from the row.
Add the sum of the removed stones' values to the player's score.
Place a new stone, whose value is equal to that sum, on the left side of the row.

The game stops when only one stone is left in the row.

The score difference between Alice and Bob is (Alice's score - Bob's score). Alice's goal is to maximize the score difference, and Bob's goal is the minimize the score difference.

Given an integer array stones of length n where stones[i] represents the value of the i^th stone from the left, return the score difference between Alice and Bob if they both play optimally.

Example 1:

Input: stones = [-1,2,-3,4,-5]
Output: 5
Explanation:
- Alice removes the first 4 stones, adds (-1) + 2 + (-3) + 4 = 2 to her score, and places a stone of
  value 2 on the left. stones = [2,-5].
- Bob removes the first 2 stones, adds 2 + (-5) = -3 to his score, and places a stone of value -3 on
  the left. stones = [-3].
The difference between their scores is 2 - (-3) = 5.

Example 2:

Input: stones = [7,-6,5,10,5,-2,-6]
Output: 13
Explanation:
- Alice removes all stones, adds 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 to her score, and places a
  stone of value 13 on the left. stones = [13].
The difference between their scores is 13 - 0 = 13.

Example 3:

Input: stones = [-10,-12]
Output: -22
Explanation:
- Alice can only make one move, which is to remove both stones. She adds (-10) + (-12) = -22 to her
  score and places a stone of value -22 on the left. stones = [-22].
The difference between their scores is (-22) - 0 = -22.

Constraints:

n == stones.length
2 <= n <= 10⁵
-10⁴ <= stones[i] <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

This problem can be modeled as a minimax game. Since both players play optimally, we can use dynamic programming to find the best possible outcome for Alice. The key is to simplify the game state. A crucial observation is that any move results in a new stone whose value is a prefix sum of the original stones array. This allows us to define the state of the game by a single index i, representing that the current row of stones is [prefix[i], s_i, s_{i+1}, ..., s_{n-1}], where prefix[i] is the sum of the first i original stones.

Let dp[i] be the maximum score difference the current player can achieve starting from state i. The goal is to compute the result for Alice's first move.

Algorithm

First, precompute the prefix sums of the stones array. Let prefix[k] be the sum of stones[0] through stones[k-1].
Let dp[i] be the maximum score difference the current player can achieve starting from a game state where the stones are effectively [prefix[i], stones[i], ..., stones[n-1]].
The base case is dp[n] = 0, as state n implies the game has ended for the player whose turn it is.
We compute the dp table backwards from i = n-1 down to 1.
The recurrence relation is dp[i] = max_{j=i+1}^{n} (prefix[j] - dp[j]). This is because from state i, a player can choose to transition to any state j > i, gaining prefix[j] points and giving the turn to the opponent, who will then score dp[j] from the new state.
The final answer is dp[1], which represents Alice's optimal score difference from her first move choices.

Walkthrough

First, we precompute the prefix sums of the stones array. Let prefix[k] be the sum of the first k stones. prefix[k] = stones[0] + ... + stones[k-1].

The DP state dp[i] represents the maximum score difference the current player can obtain when the game is in a state where the stones are effectively [prefix[i], stones[i], ..., stones[n-1]]. The player whose turn it is can choose to merge the first k stones, where k > 1. This corresponds to choosing an index j from i+1 to n.

If the player chooses j, they merge the first stone prefix[i] with the next j-i stones (stones[i] to stones[j-1]). The sum of these stones is prefix[j]. This becomes the player's score for this turn. The game then transitions to state j, and it's the other player's turn. The other player will play optimally from state j and achieve a score difference of dp[j]. Therefore, the current player's score difference for choosing j is prefix[j] - dp[j].

Since the player wants to maximize their score difference, they will choose j that maximizes this value. This gives us the recurrence relation: dp[i] = max_{j=i+1}^{n} (prefix[j] - dp[j])

The base case is dp[n] = 0, as state n means there's only one stone left (prefix[n]), and the game has ended for the player who is about to move.

We can compute the dp table backwards from i = n-1 down to 1.

The final answer is the maximum score difference Alice can achieve on her first move. She starts with the original stones array. She can choose to merge the first x stones, where x is from 2 to n. This gives her a score of prefix[x] and transitions the game to state x for Bob. Bob will then achieve dp[x]. Alice's net difference is prefix[x] - dp[x]. She will choose x to maximize this. The answer is max_{x=2}^{n} (prefix[x] - dp[x]), which is exactly dp[1].

1class Solution {2    public int stoneGameVIII(int[] stones) {3        int n = stones.length;4        long[] prefix = new long[n + 1];5        for (int i = 0; i < n; i++) {6            prefix[i + 1] = prefix[i] + stones[i];7        }8 9        long[] dp = new long[n + 1];10        // dp[n] is implicitly 011 12        for (int i = n - 1; i >= 1; i--) {13            long maxVal = Long.MIN_VALUE;14            for (int j = i + 1; j <= n; j++) {15                maxVal = Math.max(maxVal, prefix[j] - dp[j]);16            }17            dp[i] = maxVal;18        }19 20        return (int) dp[1];21    }22}

Complexity

Time

O(n^2) - Calculating prefix sums takes O(n). The nested loops for the DP calculation take O(n^2) time.

Space

O(n) - We use O(n) space for the prefix sum array and O(n) for the dp array.

Trade-offs

Pros

It's a direct and intuitive translation of the game's recurrence relation.
It correctly solves the problem for smaller constraints.

Cons

The O(n^2) time complexity is too slow for the given constraints (n <= 10^5), resulting in a 'Time Limit Exceeded' error on most platforms.

The O(n^2) DP approach can be optimized by observing a relationship between dp[i] and dp[i-1]. This optimization reduces the time complexity to linear, making it efficient enough to pass the given constraints.

Algorithm

First, create a prefix sum array prefix of size n+1.
The recurrence dp[i] = max_{j=i+1}^{n} (prefix[j] - dp[j]) can be optimized. By observing that dp[i-1] = max(prefix[i] - dp[i], dp[i]), we can compute each DP state in O(1) time.
We can compute the DP values backwards. The base case is dp[n-1] = prefix[n] (since from state n-1, the only move is to take all remaining stones, scoring prefix[n]).
We can use a single variable, say dp_val, to store the DP value of the next state (dp[i+1]) while computing the current state (dp[i]).
Initialize dp_val = prefix[n]. This represents dp[n-1].
Iterate i from n-2 down to 1.
- In each step, update dp_val using the optimized recurrence: dp_val = max(dp_val, prefix[i+1] - dp_val). This new dp_val is dp[i].
After the loop, dp_val will hold the value of dp[1], which is the final answer.

Walkthrough

The recurrence relation from the previous approach is: dp[i] = max_{j=i+1}^{n} (prefix[j] - dp[j])

Let's write out the expressions for dp[i] and dp[i-1]: dp[i] = max(prefix[i+1] - dp[i+1], prefix[i+2] - dp[i+2], ..., prefix[n] - dp[n]) dp[i-1] = max(prefix[i] - dp[i], prefix[i+1] - dp[i+1], ..., prefix[n] - dp[n])

Notice that the terms in the max for dp[i-1] are prefix[i] - dp[i] and all the terms from the max for dp[i]. This means we can rewrite dp[i-1] in terms of dp[i]: dp[i-1] = max(prefix[i] - dp[i], dp[i])

This simplified recurrence allows us to compute each dp value in O(1) time, given the next value. We can still compute the dp table backwards.

The base case remains dp[n] = 0. For i = n-1, the only choice is j=n, so dp[n-1] = prefix[n] - dp[n] = prefix[n]. Then, we can iterate from i = n-2 down to 1 using the optimized recurrence: dp[i] = max(prefix[i+1] - dp[i+1], dp[i+1]). The final answer is still dp[1].

This approach can be further space-optimized. Since dp[i] only depends on dp[i+1], we don't need to store the entire dp array. We can use a single variable to keep track of the previous dp value (dp[i+1]) while computing the current one (dp[i]).

1class Solution {2    public int stoneGameVIII(int[] stones) {3        int n = stones.length;4        long[] prefix = new long[n + 1];5        for (int i = 0; i < n; i++) {6            prefix[i + 1] = prefix[i] + stones[i];7        }8 9        // dp[i] represents the optimal score difference for the current player10        // starting from state i.11        // State i: stones are [prefix[i], stones[i], ..., stones[n-1]]12        // The final answer is dp[1].13 14        // We can use a single variable to store the dp value as we iterate backwards.15        // Let's call it `dp_val`. It will hold dp[i+1] at the start of the loop for i.16        17        // Base case: dp[n-1] = prefix[n].18        // (The only move from state n-1 is to take all remaining stones, score prefix[n])19        long dp_val = prefix[n];20 21        // Iterate from i = n-2 down to 1 to compute dp[n-2], ..., dp[1].22        for (int i = n - 2; i >= 1; i--) {23            // At this point, dp_val holds dp[i+1].24            // We compute dp[i] = max(dp[i+1], prefix[i+1] - dp[i+1])25            // and update dp_val to be dp[i] for the next iteration.26            dp_val = Math.max(dp_val, prefix[i + 1] - dp_val);27        }28 29        return (int) dp_val;30    }31}

Complexity

Time

O(n) - We iterate once to compute prefix sums and once more for the DP calculation.

Space

O(n) - The prefix sum array requires O(n) space. The DP calculation itself uses O(1) extra space.

Trade-offs

Pros

Highly efficient with linear time complexity.
Solves the problem within the given constraints.
The space-optimized version is memory efficient.

Cons

The derivation of the optimized recurrence is less intuitive than the straightforward O(n^2) DP approach.

Solutions

Solution

1class Solution {2private3  Integer[] f;4private5  int[] s;6private7  int n;8public9  int stoneGameVIII(int[] stones) {10    n = stones.length;11    f = new Integer[n];12    for (int i = 1; i < n; ++i) {13      stones[i] += stones[i - 1];14    }15    s = stones;16    return dfs(1);17  }18private19  int dfs(int i) {20    if (i >= n - 1) {21      return s[i];22    }23    if (f[i] == null) {24      f[i] = Math.max(dfs(i + 1), s[i] - dfs(i + 1));25    }26    return f[i];27  }28}

1class Solution {2public:3  int stoneGameVIII(vector<int> &stones) {4    int n = stones.size();5    for (int i = 1; i < n; ++i) {6      stones[i] += stones[i - 1];7    }8    int f[n];9    memset(f, -1, sizeof(f));10    function<int(int)> dfs = [&](int i) -> int {11      if (i >= n - 1) {12        return stones[i];13      }14      if (f[i] == -1) {15        f[i] = max(dfs(i + 1), stones[i] - dfs(i + 1));16      }17      return f[i];18    };19    return dfs(1);20  }21};

1class Solution:2    def stoneGameVIII(self, stones: List[int]) -> int: @ cache def dfs(i: int) -> int: if i >= len(stones) - 1: return s[- 1] return max(dfs(i + 1), s[i] - dfs(i + 1)) s = list(accumulate(stones)) return dfs(1)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem