LeetCode Entry

1872. Stone Game VIII

24.08.2026 hard 2026 kotlin rust

Alice maximize and Bob minimize the (A-B)

1872. Stone Game VIII hard substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1461

Problem TLDR

Alice maximize and Bob minimize the (A-B)

Intuition

Didn’t solve because misunderstood the problem: it is not the abs difference. The (A-B) is symmetrical: Alice wants minimize Bob, Bob wants minimize Alice, both want maximize themselves. After that, problem is a trivial take/skip dp.

Approach

• final condition must not be zero, because the last value could be negative

Complexity

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

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

Code

    fun stoneGameVIII(s: IntArray) = s.scan(0, Int::plus).run {
        (size-2 downTo 2).fold(last()) { ans, i -> max(ans, get(i)-ans) }
    }

    pub fn stone_game_viii(mut s: Vec<i32>) -> i32 {
        for i in 1..s.len() { s[i] += s[i - 1] }
        let last = s.pop().unwrap();
        s[1..].iter().rfold(last, |ans, &x| ans.max(x - ans))
    }