Welcome to Subscribe On Youtube
486. Predict the Winner
Description
You are given an integer array nums
. Two players are playing a game with this array: player 1 and player 2.
Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of 0
. At each turn, the player takes one of the numbers from either end of the array (i.e., nums[0]
or nums[nums.length  1]
) which reduces the size of the array by 1
. The player adds the chosen number to their score. The game ends when there are no more elements in the array.
Return true
if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return true
. You may assume that both players are playing optimally.
Example 1:
Input: nums = [1,5,2] Output: false Explanation: Initially, player 1 can choose between 1 and 2. If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. Hence, player 1 will never be the winner and you need to return false.
Example 2:
Input: nums = [1,5,233,7] Output: true Explanation: Player 1 first chooses 1. Then player 2 has to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233. Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
Constraints:
1 <= nums.length <= 20
0 <= nums[i] <= 10^{7}
Solutions

class Solution { public boolean PredictTheWinner(int[] nums) { int n = nums.length; int[][] f = new int[n][n]; for (int i = 0; i < n; ++i) { f[i][i] = nums[i]; } for (int i = n  2; i >= 0; i) { for (int j = i + 1; j < n; ++j) { f[i][j] = Math.max(nums[i]  f[i + 1][j], nums[j]  f[i][j  1]); } } return f[0][n  1] >= 0; } }

class Solution { public: bool PredictTheWinner(vector<int>& nums) { int n = nums.size(); int f[n][n]; memset(f, 0, sizeof(f)); for (int i = 0; i < n; ++i) { f[i][i] = nums[i]; } for (int i = n  2; ~i; i) { for (int j = i + 1; j < n; ++j) { f[i][j] = max(nums[i]  f[i + 1][j], nums[j]  f[i][j  1]); } } return f[0][n  1] >= 0; } };

class Solution: def PredictTheWinner(self, nums: List[int]) > bool: n = len(nums) f = [[0] * n for _ in range(n)] for i, x in enumerate(nums): f[i][i] = x for i in range(n  2, 1, 1): for j in range(i + 1, n): f[i][j] = max(nums[i]  f[i + 1][j], nums[j]  f[i][j  1]) return f[0][n  1] >= 0

func PredictTheWinner(nums []int) bool { n := len(nums) f := make([][]int, n) for i, x := range nums { f[i] = make([]int, n) f[i][i] = x } for i := n  2; i >= 0; i { for j := i + 1; j < n; j++ { f[i][j] = max(nums[i]f[i+1][j], nums[j]f[i][j1]) } } return f[0][n1] >= 0 }

function PredictTheWinner(nums: number[]): boolean { const n = nums.length; const f: number[][] = new Array(n).fill(0).map(() => new Array(n).fill(0)); for (let i = 0; i < n; ++i) { f[i][i] = nums[i]; } for (let i = n  2; i >= 0; i) { for (let j = i + 1; j < n; ++j) { f[i][j] = Math.max(nums[i]  f[i + 1][j], nums[j]  f[i][j  1]); } } return f[0][n  1] >= 0; }

impl Solution { #[allow(dead_code)] pub fn predict_the_winner(nums: Vec<i32>) > bool { let n = nums.len(); let mut dp: Vec<Vec<i32>> = vec![vec![0; n]; n]; // Initialize the dp vector for i in 0..n { dp[i][i] = nums[i]; } // Begin the dp process for i in (0..n  1).rev() { for j in i + 1..n { dp[i][j] = std::cmp::max( // Take ith num nums[i]  dp[i + 1][j], // Take jth num nums[j]  dp[i][j  1] ); } } dp[0][n  1] >= 0 } }