LeetCode Entry

1140. Stone Game II

09.08.2026 medium 2026 kotlin rust

Max Alice sum play optimally with Bob

1140. Stone Game II medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1446

Problem TLDR

Max Alice sum play optimally with Bob

Intuition

Dfs + memo depending on the current position and previous M. Inside it iterate to choose between how many indexes to take. Subtract Bob’s result from the total remaining sum.

Approach

• precompute suffix sums

Complexity

• Time complexity: \(O(n^3)\)

• Space complexity: \(O(n^2)\)

Code

    pub fn stone_game_ii(mut p: Vec<i32>) -> i32 {
        let (n, mut d) = (p.len(), [[0; 303]; 303]);
        for i in (0..n - 1).rev() { p[i] += p[i + 1] }
        for i in (0..n).rev() { for m in 1..=n {
            d[i][m] = p[i]-(1..=2 * m).map(|x| d[i + x][m.max(x)]).min().unwrap()
        }} d[0][1]
    }

    fun stoneGameII(p: IntArray): Int {
        val dp = HashMap<Int, Int>(); for (i in p.size-2 downTo 0)p[i]+=p[i+1]
        fun d(i: Int, m: Int): Int =  if (i < p.size) dp.getOrPut(m*100+i) {
            p[i]-(i..<i+2*m).minOf { x -> d(x+1,max(m, x-i+1)) }
        } else 0
        return d(0, 1)
    }