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 )
