1197. Predict the Winner

MediumDynamic ProgrammingInterval DPGame Theory

Two players take turns picking a number from either end of the array nums, adding it to their score. Assuming both play optimally, return true if the first player can end with a score at least as high as the second player. The input is JSON {nums}.

Input: JSON {nums}.

Output: Boolean — true if the first player can win or tie.

Examples

Example 1
Input: {"nums":[1,5,2]}
Output: false
Explanation: Player 2 can force at least a tie.
Example 2
Input: {"nums":[1,5,233,7]}
Output: true
Explanation: Player 1 wins.
Example 3
Input: {"nums":[1]}
Output: true
Explanation: Player 1 takes everything.

Constraints

Asked by

AmazonGoogleMicrosoftBloombergMeta
Solve this problem in the editor →