Optimal Game Strategy

#1

have i done right?

#2

@i_am_dekard_shaw
Hello Abdullah,
please check your base case

#3

@aman212yadav whats wrong with that?

#4

@i_am_dekard_shaw
your recurrence relation (say f(arr,i,j)) for this problem should be something like
if piyush turn then
return max(arr[i]+f(arr,i+1,j),arr[j]+f(arr,i,j-1))
if nimit turn then
return min(f(arr,i+1,j),f(arr,i,j-1))

#5

@i_am_dekard_shaw
please dry run your code on following testcase
2
3 4

#6

@aman212yadav but whats wrong with the base case?

#7

@i_am_dekard_shaw
for the test i mentioned above your code will never hit the base case( and u will get tle because of infinite recursion).
if u will dry run on the above test case you will find ur mistake.

#8

@aman212yadav i have made some changes …is this correct?

#9

@i_am_dekard_shaw
brother i think you forget to press save button

#10

@aman212yadav woops!!!

#11

@i_am_dekard_shaw
everthing in ur code is correct .only u missed one base case. u should handle case when their is only two elements in your array .in this case u should return maximum among two.
something like
image

btw your recurrence relation is impressive😎

1 Like
#12

@aman212yadav thanks got it