1872

1872. Stone Game VIII (Hard)

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

Companies:
Infosys

Related Topics:
Dynamic Programming

Similar Questions:

• Stone Game (Medium)
• Stone Game II (Medium)
• Stone Game III (Hard)
• Stone Game IV (Hard)
• Stone Game V (Hard)
• Stone Game VI (Medium)
• Stone Game VII (Medium)
• Stone Game VIII (Hard)

Solution 1. DP

Let prefix sum prefix[i] = A[0] + ... + A[i].

Let dp[i] be the maximum score difference the current player can get when the game starts at i, i.e. stones 0 ~ i are already merged as a new stone i whose value is prefix[i].

Consider dp[i]: assume the current player chooses to merge stones 0 ~ j (i < j < N), according to the dp definition, the maximum score difference the next player can get using the remaining stones is dp[j]. So the score difference the current player gets is prefix[j] - dp[j].

The current player will need to try all i < j < N and use the maximum prefix[j] - dp[j] as dp[i]. Thus, we have:

dp[i] = max( prefix[j] - dp[j] | i < j <= N - 2 )
dp[N - 2] = prefix[N - 1] // when there are only two stones left, the current player must take them all

The anser is dp[0].

We can simplify the above formula into the following form. In this way, dp doesn't have to be an array; we just need to store the latest dp value.

dp[i] = max( dp[i + 1], prefix[i + 1] - dp[i + 1] )   where 0 <= i < N - 2
dp[N - 2] = prefix[N - 1]

// OJ: https://leetcode.com/problems/stone-game-viii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int stoneGameVIII(vector<int>& A) {
        int N = A.size();
        for (int i = 1; i < N; ++i) A[i] += A[i - 1]; // now A[i] is the prefix sum, i.e. prefix[i]
		int dp = A.back(); // dp[N - 2] = prefix[N - 1]
        for (int i = N - 2; i > 0; --i) dp = max(dp, A[i] - dp); // dp[i - 1] = max(dp[i], A[i] - dp[i]) 
        return dp; // dp[0]
    }
};

Or use STL functions to minify code.

// OJ: https://leetcode.com/problems/stone-game-viii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int stoneGameVIII(vector<int>& A) {
        partial_sum(begin(A), end(A), begin(A));
        return accumulate(next(rbegin(A)), prev(rend(A)), A.back(), [](int memo, int cur) { return max(memo, cur - memo); });
    }
};

Or one liner in python.

# OJ: https://leetcode.com/problems/stone-game-viii/
# Author: github.com/lzl124631x
class Solution:
    def stoneGameVIII(self, A: List[int]) -> int:
        return reduce(lambda memo, cur : max(memo, cur - memo), list(accumulate(A))[::-1][:-1])