in this testcases if nitin picks 1st coin then piyush can pick 3rd coin and ans would be 7 which is max
but why it is 6
Optimal game strategy
hello @vanisinghal0201
nitin will pick 3 becuase they both are playing optimally . they will try their best to defeat other player.
pls refer ->
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.
if we consider that piyush will pick 1 coin first then in every case it will be minimum it will be max only when he picks from last coin
a)given array is not sorted.
b) nimit is also playing optimally. so he will try to minimise piyush score(ie maximise his own score).
that is why we are doing
coins[i]+ min(…) // min becuase nimit will try to reduce ur score.
similary.
coins[j]+min(…)
and piyush will choose maximum among above two case.
i didnt understand how will recursion work in this case means how to dry run it
your recursive solution is correct. use dynamic programming to optimise it furthur.
refer this article -> https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/
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.