# 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& stones) { const int n = stones.size(); vector prefix(n); // dp[i] := max score diff the current player can get when the game starts // At i, i.e., stones[0..i] are merged whose value is prefix[i] vector dp(n, INT_MIN); partial_sum(begin(stones), end(stones), begin(prefix)); // 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; } }; 
  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] := max score diff the current player can get when the game starts // At i, i.e., stones[0..i] are merged whose value is 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; } } 
  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] := max score diff the current player can get when the game starts # At i, i.e., stones[0..i] are merged whose value is 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