optimal game st.
starting piyush choose -4
nimit choose 1 bcoz we want to find out maximum value of coin piyush can have
piyush choose 3
nimit choose 2
ans should be 7
where i am wrong in this question??
Want to know question properly
No incoorect both play optimally
So if we pick 4 then he picks 3 ,then we pick 2 and he picks 1
Also picking the greatest always won’t help ,say
4
100 1000 10 90
Here I will pick 90 first so that opponent don’t get access to 1000 and he will pick 100 then I pick 1000
and he picks 10 so answer is 1090
So this means its not always the greatest we pick .’
logic:
Remember both A and B are equally smart and we want A to get maximum.
if coins are indexed from i to j and both have to choose one out of two ends.
case 1: if A chooses a[i], now opponent can choose either a[i+1] or a[j] whatever is maximum out of two. which means A will get Minimum in his next chance based on opponent choice.
case 1.a: if opponent choose a[i+1], player will chose either a[i+2] or or a[j]
case 1.b: if opponent choose a[j], player will chose either a[i+1] or or a[j-1]
So A will get minimum out of case 1.a and case 1.b…as opponent is equally smarter and choose such a coin which give him maximum but minimum to player A.
case 2: if A chooses a[j], now opponent can choose either a[i] or a[j-1] whatever is maximum out of two. which means A will get Minimum in his next chance based on opponent choice.
case 2.a: if opponent choose a[i], player will chose either a[i+1] or or a[j-1]
case 2.b: if opponent choose a[j-1], player will chose either a[i] or or a[j-2]
So A will get minimum out of case 2.a and case 2.a…as opponent is equally smarter and choose such a coin which give him maximum but minimum to player A.
This will give you a recursive case in which final answer is max(case1,case2)
is this dp question??
no
its not,but we can apply dp as well.It will optimize the solution
DP optimizes recursive solution by the way in some cases 
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.