Skip to main content

1140. Stone Game II

medium

Alice and Bob take stones from the front of an array; each turn lets you take between 1 and 2M piles where M is a growing parameter. State is (start, M), so this is a clean 2D DP.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Alice and Bob continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones. Alice and Bob take turns, with Alice starting first. Initially, M = 1. On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X). The game continues until all the stones have been taken. Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.

Constraints

  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 10^4

Examples

Example 1

Input
piles = [2,7,9,4,4]
Output
10

Explanation: If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger.

Example 2

Input
piles = [1,2,3,4,5,100]
Output
104

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

State: (i, M) where i is the next pile index and M is the current cap parameter. Action: choose x in [1, 2M], take piles[i..i+x-1], opponent plays from (i+x, max(M, x)).

Hint 2

dp[i][M] = maximum stones the current player can collect from suffix piles[i..] given parameter M.

Hint 3

Use suffix sums to compute the remaining total in O(1). The current player's score = totalRemaining - opponentScore.

Hint 4

dp[i][M] = max over x in [1, 2M] of (suffixSum[i] - dp[i+x][max(M, x)]).

Solution approach

Reveal approach

Top-down memoization on (i, M). Precompute suffix sums so totalRemaining(i) is O(1). Base case: if i >= n, return 0. If i + 2*M >= n the current player can take everything remaining, so return suffixSum[i]. Recurrence: dp[i][M] = max over x in [1, 2M] of suffixSum[i] - dp[i+x][max(M, x)] — the current player gets the suffix minus whatever the opponent claims from the position after this move. Answer is dp[0][1]. Cap M by n / 2 + 1 since once 2M >= n - i the recursion bottoms out. Bottom-up sweeps i from n down to 0.

Complexity

Time
O(n^3)
Space
O(n^2)

Related patterns

  • dynamic-programming
  • game-theory
  • prefix-sum

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

Practice these live with InterviewChamp.AI

Drill Stone Game II and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →