Optimal Game Strategy 1

#1

Can you give me some test case in which my code will fail …


this is my code …

#2

5, 3, 7, 10
Ans 15
You made a big assumption in code that if one starts picking from start he will pick all number from start or he will pick all numbers from end.
Use DP for this problem. In each step try to see which move you should make, such that your opponent does not have get much benifit.

#3

now tell me any test case for which my code will fail.
for 5,3,7,10 it’ll give 15 as i have sorted the array
complexity will be nlogn

#4

11 10 9 12 8 6 10 2
Ans 38
Your answer 37.
You are approaching the problem in a very wrong way, aim should never be to just pass the given test case by some hack. Always try to figure-out how to get the right solution and efficient solution.
Try to implement the DP solution
F(i, j) = Max(Vi + min(F(i+2, j), F(i+1, j-1) ),
Vj + min(F(i+1, j-1), F(i, j-2) ))

#5

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.