Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1872.html
1872. Stone Game VIII
Level
Hard
Description
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 leftmostx
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 to 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 <= 10^5
10^4 <= stones[i] <= 10^4
Solution
First, calculate the prefix sums of stones
such that prefixSums[i]
is the sum of all elements from stones[0]
to stones[i]
. Then use dynamic programming. Create an array dp
of length n
such that dp[i]
represents the maximum difference if Alice chooses x = i + 1
for the first time. Obviously, dp[n  1] = prefixSums[n  1]
. For i
from n  2
to 1, there is dp[i] = prefixSums[i]  maxDiff
, where maxDiff
is the maximum value from dp[i + 1]
to dp[n  1]
. Update maxDiff
at each index. Finally, return maxDiff
.

class Solution { public int stoneGameVIII(int[] stones) { int length = stones.length; if (length == 2) return stones[0] + stones[1]; int[] prefixSums = new int[length]; prefixSums[0] = stones[0]; for (int i = 1; i < length; i++) prefixSums[i] = prefixSums[i  1] + stones[i]; int[] dp = new int[length]; dp[length  1] = prefixSums[length  1]; int maxDiff = dp[length  1]; for (int i = length  2; i > 0; i) { dp[i] = prefixSums[i]  maxDiff; maxDiff = Math.max(maxDiff, dp[i]); } return maxDiff; } } ############ class Solution { public int stoneGameVIII(int[] stones) { int n = stones.length; int[] preSum = new int[n]; preSum[0] = stones[0]; for (int i = 1; i < n; ++i) { preSum[i] = preSum[i  1] + stones[i]; } int f = preSum[n  1]; for (int i = n  2; i > 0; i) { f = Math.max(f, preSum[i]  f); } return f; } }

// OJ: https://leetcode.com/problems/stonegameviii/ // 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] } };

class Solution: def stoneGameVIII(self, stones: List[int]) > int: pre_sum = list(accumulate(stones)) f = pre_sum[len(stones)  1] for i in range(len(stones)  2, 0, 1): f = max(f, pre_sum[i]  f) return f ############ # 1872. Stone Game VIII # https://leetcode.com/problems/stonegameviii/ class Solution: def stoneGameVIII(self, stones: List[int]) > int: n = len(stones) for i in range(1, n): stones[i] += stones[i1] dp = stones[1] for i in range(n  2, 0, 1): dp = max(dp, stones[i]  dp) return dp

func stoneGameVIII(stones []int) int { n := len(stones) for i := 1; i < n; i++ { stones[i] += stones[i1] } f := stones[n1] for i := n  2; i > 0; i { f = max(f, stones[i]f) } return f }

function stoneGameVIII(stones: number[]): number { const n = stones.length; for (let i = 1; i < n; ++i) { stones[i] += stones[i  1]; } let f = stones[n  1]; for (let i = n  2; i; i) { f = Math.max(f, stones[i]  f); } return f; }