I cannot understand my mistake

#1

optimal game strategy

#2

Hello @Daniyal-Farooque-446199309332205,

You have to find the maximum value that Piyush can win with if he moves first.
Example:
6
4 5 6 2 1 3
Your Code’s Wrong Output:
13

Can you explain the output?
Let me know if you fails to correct it.

Hope, this would help.

#3

i updated the code still cannot pass the testcases.

#4

for optimal solution i am checking that the coin which is being chosen doesn’t have a coin next to it which makes the opposite’s sum bigger.

#5

Hello @Daniyal-Farooque-446199309332205,

There are two choices:

  1. The user chooses the ith coin with value Vi: The opponent either chooses (i+1)th coin or jth coin. The opponent intends to choose the coin which leaves the user with minimum value.
    i.e. The user can collect the value Vi + min(F(i+2, j), F(i+1, j-1) )

    image
    image721×315 4.4 KB

  2. The user chooses the jth coin with value Vj: The opponent either chooses ith coin or (j-1)th coin. The opponent intends to choose the coin which leaves the user with minimum value.
    i.e. The user can collect the value Vj + min(F(i+1, j-1), F(i, j-2) )
    image

Following is recursive solution that is based on above two choices. We take the maximum of two choices.

F(i, j) represents the maximum value the user can collect from
i’th coin to j’th coin.

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

Base Cases

F(i, j)  = Vi           If j == i
F(i, j)  = max(Vi, Vj)  If j == i+1