Optimal Game Strategy-1

#1

testcases are not passing

#2

@RULEREMPIRES bro your approach is completely flawed. Here both the players are clever, both want that the other one pick up minimum one.

For test case :-
4
5 4 8 6
your answer :- 11
actual :- 13

We have a correct approach for this problem and that is this.

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.
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.

#3

@RULEREMPIRES so try to build ya logic for the approach i told you!

#4
#5

i tried but still first testcaseshows wrong answer

#6

@RULEREMPIRES bro there is no need to explicitly specify odd even cases. Here I am posting my code for your reference. You are not moving on the correct approach I mentioned in algorithm.


It is basically a dynamic programming problem, now you have the code so draw recursion tree for the code and analyze overlapping subproblems in it.
Also always mark the doubts resolved after your query is clear.
Buddy for sure do some work by dry running the code. I want you to learn more.