Problem Description
Alice and Bob take turns playing a game, with Alice starting first. There are n stones arranged in a row. Each player on their turn will choose an integer x > 1, remove the leftmost x stones from the row, add the sum of the removed stones' values to their score, and 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. The score difference between Alice and Bob is defined as (Alice's score - Bob's score). Alice's goal is to maximize this score difference, while Bob's goal is to minimize it. Given an integer array stones of length n, return the score difference between Alice and Bob if they both play optimally.
Key Insights
- Players can only remove stones in groups greater than one (x > 1).
- The game continues until only one stone remains.
- The sum of removed stones becomes the new stone placed back, influencing future moves.
- Both players aim to optimize their scores: Alice wants to maximize the difference, while Bob wants to minimize it.
- A greedy approach along with prefix sums can effectively determine optimal moves.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
The problem can be solved using a greedy strategy combined with prefix sums. First, we calculate the prefix sums of the stones to efficiently compute the sum of removed stones in constant time. The key idea is to iterate through the prefix sums from the end of the array to the beginning, maintaining the best score difference possible at each step. Alice will always try to maximize the score difference, while Bob will minimize it. The final score difference is obtained after processing all possible moves.