Skip to content

1872. Stone Game VIII 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int stoneGameVIII(vector<int>& stones) {
    const int n = stones.size();
    vector<int> prefix(n);
    // dp[i] := the maximum score difference the current player can get when the
    // game starts at i, i.e. stones[0..i] are merged into the value prefix[i]
    vector<int> dp(n, INT_MIN);

    partial_sum(stones.begin(), stones.end(), prefix.begin());

    // Must take all when there're only two stones left.
    dp[n - 2] = prefix.back();

    for (int i = n - 3; i >= 0; --i)
      dp[i] = max(dp[i + 1], prefix[i + 1] - dp[i + 1]);

    return dp[0];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int stoneGameVIII(int[] stones) {
    final int n = stones.length;
    int[] prefix = stones.clone();
    // dp[i] := the maximum score difference the current player can get when the
    // game starts at i, i.e. stones[0..i] are merged into the value prefix[i]
    int[] dp = new int[n];
    Arrays.fill(dp, Integer.MIN_VALUE);

    for (int i = 1; i < prefix.length; ++i)
      prefix[i] += prefix[i - 1];

    // Must take all when there're only two stones left.
    dp[n - 2] = prefix[n - 1];

    for (int i = n - 3; i >= 0; --i)
      dp[i] = Math.max(dp[i + 1], prefix[i + 1] - dp[i + 1]);

    return dp[0];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def stoneGameVIII(self, stones: list[int]) -> int:
    n = len(stones)
    prefix = list(itertools.accumulate(stones))
    # dp[i] := the maximum score difference the current player can get when the
    # game starts at i, i.e. stones[0..i] are merged into the value prefix[i]
    dp = [-math.inf] * n

    # Must take all when there're only two stones left.
    dp[n - 2] = prefix[-1]

    for i in reversed(range(n - 2)):
      dp[i] = max(dp[i + 1], prefix[i + 1] - dp[i + 1])

    return dp[0]