> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/dynamic-programming/general/predict-the-winner.md).

# Predict the Winner

## Problem Statement

<br>

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.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [1,5,2]
</strong><strong>Output: false
</strong><strong>Explanation: Initially, player 1 can choose between 1 and 2. 
</strong>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.
</code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [1,5,233,7]
</strong><strong>Output: true
</strong><strong>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.
</strong>Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
</code></pre>

&#x20;

**Constraints:**

* `1 <= nums.length <= 20`
* `0 <= nums[i] <= 107`\ <br>

## Intuition

```
No need to maintain two scores sepeately

Just add for player 1 and subtract for player 2
In end if ans is +ve return true 


```

### Links

<https://leetcode.com/problems/predict-the-winner/description/>

### Video Links

<https://www.youtube.com/watch?v=OO7KUGUJHRs&ab_channel=C0deSutra>

### Approach 1:

```
Recursion        
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int winner(vector<int>& nums, int start, int end){
        if(start == end)
            return nums[start];

        int left = nums[start] - winner(nums, start+1, end);
        int right = nums[end] - winner(nums, start, end-1);

        return max(left, right);
    }

    bool PredictTheWinner(vector<int>& nums) {
        int ans = winner(nums, 0, nums.size()-1);

        return ans>=0 ? true : false;
    }
};
```

{% endcode %}

### Approach 2:

```
Memoization
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int winner(vector<int>& nums, int start, int end, vector<vector<int>> &dp){
        if(start == end)
            return nums[start];
            
        if(dp[start][end] != -1)
            return dp[start][end];

        int left = nums[start] - winner(nums, start+1, end, dp);
        int right = nums[end] - winner(nums, start, end-1, dp);

        return dp[start][end] = max(left, right);
    }

    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n,-1));
        int ans = winner(nums, 0, nums.size()-1, dp);
        
        return ans>=0 ? true : false;
    }
};
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems