Leetcode 1240 Solution

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        cache = {}

        def play(piles, s, i, M):
            if i == len(piles):
                return 0

            key = (i, M)
            if key in cache:
                return cache[key]

            start_pile = i
            end_pile = i

            options = []

            pile_sum = 0
            while end_pile < len(piles) and end_pile - start_pile + 1 <= 2 * M:
                pile_sum += piles[end_pile]
                s -= piles[end_pile]

                opponent_opt = play(piles, s, end_pile + 1, max(end_pile - start_pile + 1, M))

                options.append(pile_sum + s - opponent_opt)

                end_pile += 1

            cache[key] = max(options)
            return cache[key]

        return play(piles, sum(piles), 0, 1)