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.
Note: The opponent is as clever as the user.
Determine the maximum possible amount of money we can definitely win if we move first.
Eg A = [5, 4, 8, 10]
O/P : 15
Explanation :
You : Pick 10
Opponent : Pick 8
You : Pick 5
Opponent : Pick 4Total amount with you : 10 + 5 = 15
Note : One thought can come in our mind to always select the max value element (leftmost/rightmost) and proceed but this will not always give an optimal answer
Eg {3,9,1,2}
User selects max (3,2) = 3 arr[]={9,1,2}
Opponent selects max(9,2) = 9 arr[]={1,2}
User selects max(1,2) = 2 arr[]={1}
Opponent selects max(1) = 1 arr[]={}
Total amount of user = 3 + 2 =5
Total amount of Opponent= 9+ 1=10
Clearly User i.e we lost ! So this approach fails !
Now this problem is related to Minimax Algorithm
Minimax is a kind of backtracking algorithm that is used in decision making and game theory to find the optimal move for a player, assuming that your opponent also plays optimally.
Let’s dive deep into this !
We now know that we have to consider all the possible options since only selecting the max everytime may result in us being lost ! That’s where recursion comes !
- Suppose it’s your turn and you are left with elements in the index range [‘I’, ‘J’] (other coins have already been picked up in previous turns). You have the option to pick either i th or j th coin. Of these two options, you would select the one which maximizes your winning amount.
- If you pick the ith coin. The other player will have the option to pick (‘I’+1)th or ‘J’th element & he will choose the greater out of the two since he is as smart as you !
- After We picked the i th coin , Suppose :
- If the opponent picks the (‘I’+1)th coin , You can pick either end of the range [‘I’+2, ‘J’].
Eg {9,8,5,2,3} & We have picked '9'
- Or if the opponent picks ‘J’th coin , You can pick either end of the range [‘I’+1, ‘J’-1].
Eg {9,3,5,2,8} & We have picked '9'
- we can also say “ Opponent chooses the next Maximum element ” in another way “ the opponent will chose the element in such a way which leaves us with minimum value element(when our next turn comes) “
- Hence, of the two ranges which weare left with (mentioned above), we can only use that range that gives us the minimum amount.
- We don’t have any other option since we know that our opponent is as good as we are. So we are prepared for the worst
- Similarly If you pick the jth coin. The other player will have the option to pick ith or (‘J’-1)th coin.
- If the opponent picks the ith coin. You can pick either end of the range [‘I’+1, ‘J’-1].
Eg {8,5,2,3,9} & We have picked '9'
- If the opponent picks (‘J’-1)th coin. You can pick either end of the range [‘I’, ‘J’-2].
Eg {5,2,3,8,9} & We have picked '9'
- Similarly here, of the two ranges which you are left with (mentioned above), you can only use that range which gives us the minimum amount.
Recursive Code
int solve(int arr[], int i, int j)
{
if(i>j) return 0;
if(i==j) return arr[i];
int left = arr[i] + min(solve(arr,i+1,j-1),solve(arr,i+2,j));
int right= arr[j] + min(solve(arr,i+1,j-1),solve(arr,i,j-2));
return max(left,right);
}
int maximumAmount(int arr[], int n)
{
return solve(arr,0,n-1);
}
The above code has time complexity of O(4 ^ N) since in the worst case we can have 4 functional calls
Let’s just add 2–3 lines more to reduce the time complexity from exponential to O(N ^ 2) !
Memoizaton !
int solve(int arr[],vector<vector<int>>& dp, int i, int j)
{
if(i>j) return 0;
if(i==j) return arr[i];
if(dp[i][j]!=-1) return dp[i][j];
int left = arr[i] + min(solve(arr,dp,i+1,j-1),solve(arr,dp,i+2,j));
int right= arr[j] + min(solve(arr,dp,i+1,j-1),solve(arr,dp,i,j-2));
return dp[i][j] = max(left,right);
}
int maximumAmount(int arr[], int n)
{
vector<vector<int>> dp(n+1,vector<int>(n+1,-1));
return solve(arr,dp,0,n-1);
}
Ta Da !! We found the max amount we can have using Dynamic Programming . Now we have better chances of wining !!
Related Question : 2 players are playing a game (exactly same as above question). We have to predict whether the first player wins the game or not. The question is available on leetcode
- Approach : Find the max amount that player 1 can have ( the above question we discussed about) let that be “amount”
- If the no of elements is even , the first player will always wins no matter what so simply return true
- else in case of odd, check if twice of amount ≥ sum of the elements of the array if yes, player 1 will always win else player 2 will win
Refer here to watch the MIT video to gain more about this concept (start watching from 1:00:00 )