Approach #1 Using Recursion [Accepted]
The idea behind the recursive approach is simple. The two players Player 1 and Player 2 will be taking turns alternately. For the Player 1 to be the winner, we need . Or in other terms, .
Thus, for the turn of Player 1, we can add its score obtained to the total score and for Player 2's turn, we can substract its score from the total score. At the end, we can check if the total score is greater than or equal to zero(equal score of both players), to predict that Player 1 will be the winner.
Thus, by making use of a recursive function
winner(nums,s,e,turn) which predicts the winner for the array as the score array with the elements in the range of indices currently being considered, given a particular player's turn, indicated by being Player 1's turn and being the Player 2's turn, we can predict the winner of the given problem by making the function call
winner(nums,0,n-1,1). Here, refers to the length of array.
In every turn, we can either pick up the first() or the last() element of the current subarray. Since both the players are assumed to be playing smartly and making the best move at every step, both will tend to maximize their scores. Thus, we can make use of the same function
winner to determine the maximum score possible for any of the players.
Now, at every step of the recursive process, we determine the maximum score possible for the current player. It will be the maximum one possible out of the scores obtained by picking the first or the last element of the current subarray.
To obtain the score possible from the remaining subarray, we can again make use of the same
winner function and add the score corresponding to the point picked in the current function call. But, we need to take care of whether to add or subtract this score to the total score available. If it is Player 1's turn, we add the current number's score to the total score, otherwise, we need to subtract the same.
Thus, at every step, we need update the search space appropriately based on the element chosen and also invert the 's value to indicate the turn change among the players and either add or subtract the current player's score from the total score available to determine the end result.
Further, note that the value returned at every step is given by . This is equivalent to the statement for Player 1's turn and for Player 2's turn.
This is done because, looking from Player 1's perspective, for any move made by Player 1, it tends to leave the remaining subarray in a situation which minimizes the best score possible for Player 2, even if it plays in the best possible manner. But, when the turn passes to Player 1 again, for Player 1 to win, the remaining subarray should be left in a state such that the score obtained from this subarrray is maximum(for Player 1).
This is a general criteria for any arbitrary two player game and is commonly known as the Min-Max algorithm.
The following image shows how the scores are passed to determine the end result for a simple example.
Time complexity : . Size of recursion tree will be . Here, refers to the length of array.
Space complexity : . The depth of the recursion tree can go upto .
Approach #2 Similar Approach [Accepted]
We can omit the use of to keep a track of the player for the current turn. To do so, we can make use of a simple observation. If the current turn belongs to, say Player 1, we pick up an element, say , from either end, and give the turn to Player 2. Thus, if we obtain the score for the remaining elements(leaving ), this score, now belongs to Player 2. Thus, since Player 2 is competing against Player 1, this score should be subtracted from Player 1's current(local) score() to obtain the effective score of Player 1 at the current instant.
Similar argument holds true for Player 2's turn as well i.e. we can subtract Player 1's score for the remaining subarray from Player 2's current score to obtain its effective score. By making use of this observation, we can omit the use of from
winner to find the required result by making the slight change discussed above in the
While returning the result from
winner for the current function call, we return the larger of the effective scores possible by choosing either the first or the last element from the currently available subarray. Rest of the process remains the same as the last approach.
Now, in order to remove the duplicate function calls, we can make use of a 2-D memoization array, , such that we can store the result obtained for the function call
winner for a subarray with starting and ending indices being and ] at . This helps to prune the search space to a great extent.
This approach is inspired by @chidong
Time complexity : . The entire array of size x is filled only once. Here, refers to the size of array.
Space complexity : . array of size x is used for memoization.
Approach #3 Dynamic Programming [Accepted]:
We can observe that the effective score for the current player for any given subarray only depends on the elements within the range in the array . It mainly depends on whether the element or is chosen in the current turn and also on the maximum score possible for the other player from the remaining subarray left after choosing the current element. Thus, it is certain that the current effective score isn't dependent on the elements outside the range .
Based on the above observation, we can say that if know the maximum effective score possible for the subarray and , we can easily determine the maximum effective score possible for the subarray as . These equations are deduced based on the last approach.
From this, we conclude that we can make use of Dynamic Programming to determine the required maximum effective score for the array . We can make use of a 2-D array, such that is used to store the maximum effective score possible for the subarray . The updation equation becomes:
We can fill in the array starting from the last row. At the end, the value for gives the required result. Here, refers to the length of array.
Look at the animation below to clearly understand the filling process.
Time complexity : . x entries in array of size x is filled once. Here, refers to the length of array.
Space complexity : . array of size x is used.
Approach #4 1-D Dynamic Programming [Accepted]:
From the last approach, we see that the updation equation is:
Thus, for filling in any entry in array, only the entries in the next row(same column) and the previous column(same row) are needed.
Instead of making use of a new row in array for the current row's updations, we can overwrite the values in the previous row itself and consider the values as belonging to the new row's entries, since the older values won't be needed ever in the future again. Thus, instead of making use of a 2-D array, we can make use of a 1-D array and make the updations appropriately.
Time complexity : . The elements of array are updated times. Here, refers to the length of array.
Space complexity : . 1-D array of size is used.
Analysis written by: @vinod23