Sample Input
4
1 2 3 4
Sample Output
6
Explanation
Piyush will pick the coin 4. Then Nimit can pick either 1 or 3. In both the cases piyush picks coin 2 and wins with a total of 6.
if Nimit can pick either 1 or 3,
lets say he picks 1 and removes it then we are left with 2 3 and piyush would pick 3 then and his ans would be 7 . so there could be different outputs right?
It is mentioned in the question both the players play optimally. This means that at every step the players will choose the most optimal solution.
Example:
At first look , this looks like a Greedy problem but it is clearly not so. This can clearly be observed in a simple testcase like
4
5 4 8 6
Clearly , we would need an optimal solution for this. At each instance we would need to consider two possibilities that we can pick the first as well as the last element of the remaining array.
Both these possibilities give rise to two more possibilities depending on the other player. Since the second player plays optimally and try to minimise our score. So overall we have two possibilities at each instance.
We entertain both these cases and take the maximum result of the two and return that result.
We take two pointer variables , say ‘i’ and ‘j’ which each represent the starting and the ending point of the remaining array currently in consideration. We work till the two pointers cross each other.
https://ide.codingblocks.com/s/251314 corrected code.
Use long instead of int. And you needn’t pass the player char.
ok i will see the corrected code
you can test your code for the following input. It will give a wrong answer for the test case:
10
22 50 16 13 8 41 25 43 8 7
Correct answer: 154
Your answer: 79
okay will test it , let me dry run your code and understand your approach ,if i cant i will get back to you .
yes my answer is 79 … according to the question at each turn either first or last can be chosen and since largest value has to be calculated so the best option will be chosen at each turn and piyush will start, so for the above test case:-
could you tell me how 154 will come in the answer?
// Consider both the possibilities. You can pick either the first or the last
// coin.
// Since the opponent plays optimally , we would get the minimum of the
// remaining coins for each choice.
Then just take the max of these 2.
Since both players play optimally this means, both will choose the maximum coins available to them.
Similarly, see this test case:
4
4 15 3 2
Case 1: Piyush->4, Nimit -> 15 , Piyush ->3 , Nimit ->2
Case 2: Piyush -> 2, Nimit ->4 , Piyush ->15 , Nimit ->3
In case 2 Piyush can have maximum 17 coins.
okay thanks, i have understood the code, i did dry run drew the recursion tree to understand it better but what i dont understand is how did you come up with the right recurrence relation like from thin air , because when to si+2 or ei-2 or when si+1 and ei-1 ,because when i was thinking i was accounting for the other players move by not adding the it to the last sum.,here too accounted for the other player moves …by just understanding the question is it to possible to get the right recurrence relation like this?
See, you can either pick the first coin or the last also every opponent plays optimally.
Now imagine, I pick the first element. Now you have 2 elements to choose from. You can pick either the first or the last from the side that would minimize my score.
Again, if I pick the last element. Now you have 2 elements to choose from. You can pick either the first or the last from the side that would minimize my score.
Now, we just maximize the final score by taking max of these 2 cases. The key here is that I can pick from 2 choices either the start or the end. You can do that too.
yes yes i understood this , i think maybe where i am struggling in recursion is to implement my thought process into code because everything is just assumption, unlike when solving arrays or strings like everything is much more easier to grasp and there is a simplicity to implementing also
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
