Skip to content

Latest commit

 

History

History
143 lines (84 loc) · 3.76 KB

README_EN.md

File metadata and controls

143 lines (84 loc) · 3.76 KB

1872. Stone Game VIII

中文文档

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:

    <li>Choose an integer <code>x &gt; 1</code>, and <strong>remove</strong> the leftmost <code>x</code> stones from the row.</li>

<li>Add the <strong>sum</strong> of the <strong>removed</strong> stones&#39; values to the player&#39;s score.</li>

<li>Place a <strong>new stone</strong>, whose value is equal to that sum, on the left side of the row.</li>

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:

    <li><code>n == stones.length</code></li>

<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>

<li><code>-10<sup>4</sup> &lt;= stones[i] &lt;= 10<sup>4</sup></code></li>

Solutions

Python3

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

Java

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;
    }
}

...