Space
Open
From Fieldwork
Scales
Archive
The core insight is that instead of tracking two separate scores, we track the score difference (Player 1 - Player 2).
Player 1 tries to maximize this difference.
Player 2 tries to minimize this difference (which is equivalent to maximizing their own score relative to Player 1).
It calculates the DP table diagonally or by length.
class Solution:
def PredictTheWinner(self, nums: List[int]) -> bool:
n = len(nums)
# dp[i] will eventually store the max diff for subarray ending at index j
# initialized with the base case (subarrays of length 1)
dp = nums[:]
# Iterate over the length of the subarray
# diff is the distance between left pointer (i) and right pointer (j)
for diff in range(1, n):
for i in range(n - diff):
j = i + diff
# Update dp[i] for the new range [i, j]
# dp[i+1] represents the result of range [i+1, j] (after picking left)
# dp[i] (old value) represents the result of range [i, j-1] (after picking right)
pick_left = nums[i] - dp[i + 1]
pick_right = nums[j] - dp[i]
dp[i] = max(pick_left, pick_right)
return dp[0] >= 0Practice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode