Determine winner in optimal-play card game
Overview
This question evaluates algorithmic problem-solving skills in game-theoretic optimal play and dynamic programming, including reasoning about maximum score difference, reconstruction of an optimal move sequence, and analysis of time and space complexity.
Affirm
Jul 15, 2025, 12:00 AM
Software Engineer
Onsite
Coding & Algorithms
0
0
Given a row of N cards with integer values (values may be positive, zero, or negative), two players alternately pick either the leftmost or rightmost card. Both play optimally to maximize their total sum. Implement a function winner_score(cards: List[int]) -> int that returns the maximum score difference (first − second). Then:
- Explain your time and space complexity.
- Modify the function to also return one optimal sequence of picks (as a list of indices). Constraints: 1 ≤ N ≤ 2000.