Optimal game strategy recursion

#1

sir,i have understand question but it is not matching with the example test case i think that in example there will be maximum possible value is 7.
can you give apporoch to this question with given example.
so that i could solve it.

#2

@prince43055kumar, here both player will play optimally(Playing optimally means that both players will have insight into all possible next moves and will play in such a way to maximize their chance of winning without making a mistake.) so nimit will choose the coin that will result in less value left for piyush .

so coming to the giving example it means he has choice to choose between 1 and 3 so out of which he will choose the option which is good for him .
if he had chosen 1 then nimit would have 7 with him that’s why he choose 3 thus piyush getting 6 coins
In the question it is written that both will play optimally
what you mean is the greedy approach you have to think in terms of dynammic programming

In case of any doubt feel free to ask :slight_smile:
mark your doubt as RESOLVED if you got the answer

1 Like
#3

i have send my code please look into it.

#4

your code fails for the cases like
4
8 15 3 7
where the answer should be 22 but your code produces 15.
why it is failing , in this question both players are playing optimally and you are not covering all the cases .

let me share you my approach :-
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.
For the first possibility , where we could pick the first element , the other player will pick the next element from the side that would minimise our total score.
Similarly , for the second possibility , where we can pick the last element , the other player would still pick the next element from the side that would minimise our total score.
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

refer :-

In case of any doubt feel free to ask :slight_smile:
mark your doubt as resolved if you got the answer