Test cases not being passed
You can pick coins both from the start as well as from the end. But in your code you have picked coins only from the end.
Try again and tell me if you are able to figure out the solution. Otherwise I will explain the approach to solve this question.
But in order to get the maximum value, he will pick coins from the end I suppose.
Its not given anywhere that the array of coins will be in sorted order.
The values can be in any random order.
In such type of questions, try forming the recurrence relation first
Ok I will help you in forming the recurrence relations.
Coins can be picked from either end. So we will have two values - one when coin is picked from the start and the other when coin is picked from the end. And we will return the maximum of the two values.
Let the two values be a and b, v be our array and s and e be the starting and ending indices respectively (s = 0 and e = n-1 initially).
maxvalue is the function name.
a = v[s] + min( maxvalue(v,s+2,e), maxvalue(v,s+1,e-1) );
b = v[e] + min( maxvalue(v,s+1,e-1), maxvalue(v,s,e-2) );
a is the value when the first player picks the coin from the start. So v[s] is added. Our array is from s+1 to e now. If the second player picks from the start, our search space becomes s+2 to e now and the first player will be left with maxvalue(v,s+2,e). And if he picks from the end, our search space becomes s+1 to e-1 and the first player will be left with maxvalue(v,s+1,e-1). Both players play optimally, so the second player will leave the minimum of the two values for the first player. Hence the first recurrence relation for a.
We can form the second recurrence relation for b similarly.
And finally we will return max(a,b).
Hey @S19APP-PP0108 I did exactly as you said. The sample test case is passed my my score is still zero. Please help!
In line 8, it should be l>r instead of l>=r. This is because there is one element left when l=r.
And there is no need to declare global variables for the function. Local ones will work.
Hahaha… Glad to help.
Hope you understood the concept behind it.