# Stone Game VIII
**Difficulty:** HARD
[External](https://leetcode.com/problems/stone-game-viii)
Canonical: https://scaleengineer.com/dsa/problems/stone-game-viii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory)
**Data structures:** Array
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## Problem
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:

1. Choose an integer `x > 1`, and **remove** the leftmost `x` stones from the row.
2. Add the **sum** of the **removed** stones' values to the player's score.
3. 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 `ith` 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 <= 105`
* `-104 <= stones[i] <= 104`

# Approaches
## Quadratic Time Dynamic Programming
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.
**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.
**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.
### Explanation
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]`.

```java
class Solution {
    public int stoneGameVIII(int[] stones) {
        int n = stones.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + stones[i];
        }

        long[] dp = new long[n + 1];
        // dp[n] is implicitly 0

        for (int i = n - 1; i >= 1; i--) {
            long maxVal = Long.MIN_VALUE;
            for (int j = i + 1; j <= n; j++) {
                maxVal = Math.max(maxVal, prefix[j] - dp[j]);
            }
            dp[i] = maxVal;
        }

        return (int) dp[1];
    }
}
```
### 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.

## Linear Time Dynamic Programming
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.
**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.
**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.
### Explanation
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]`).

```java
class Solution {
    public int stoneGameVIII(int[] stones) {
        int n = stones.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + stones[i];
        }

        // dp[i] represents the optimal score difference for the current player
        // starting from state i.
        // State i: stones are [prefix[i], stones[i], ..., stones[n-1]]
        // The final answer is dp[1].

        // We can use a single variable to store the dp value as we iterate backwards.
        // Let's call it `dp_val`. It will hold dp[i+1] at the start of the loop for i.
        
        // Base case: dp[n-1] = prefix[n].
        // (The only move from state n-1 is to take all remaining stones, score prefix[n])
        long dp_val = prefix[n];

        // Iterate from i = n-2 down to 1 to compute dp[n-2], ..., dp[1].
        for (int i = n - 2; i >= 1; i--) {
            // At this point, dp_val holds dp[i+1].
            // We compute dp[i] = max(dp[i+1], prefix[i+1] - dp[i+1])
            // and update dp_val to be dp[i] for the next iteration.
            dp_val = Math.max(dp_val, prefix[i + 1] - dp_val);
        }

        return (int) dp_val;
    }
}
```
### 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.

# Solutions
### Java

```java
class Solution {
private
  Integer[] f;
private
  int[] s;
private
  int n;
public
  int stoneGameVIII(int[] stones) {
    n = stones.length;
    f = new Integer[n];
    for (int i = 1; i < n; ++i) {
      stones[i] += stones[i - 1];
    }
    s = stones;
    return dfs(1);
  }
private
  int dfs(int i) {
    if (i >= n - 1) {
      return s[i];
    }
    if (f[i] == null) {
      f[i] = Math.max(dfs(i + 1), s[i] - dfs(i + 1));
    }
    return f[i];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int stoneGameVIII(vector<int> &stones) {
    int n = stones.size();
    for (int i = 1; i < n; ++i) {
      stones[i] += stones[i - 1];
    }
    int f[n];
    memset(f, -1, sizeof(f));
    function<int(int)> dfs = [&](int i) -> int {
      if (i >= n - 1) {
        return stones[i];
      }
      if (f[i] == -1) {
        f[i] = max(dfs(i + 1), stones[i] - dfs(i + 1));
      }
      return f[i];
    };
    return dfs(1);
  }
};

```

### Python

```python
class Solution:
    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)

```