Not able to understand question

#1

Is the numbers given in sorted order??

also
Piyush will pick the coin 4. Then Nimit can pick either 1 or 3. In both the cases piyush picks coin 2 and wins with a total of 6.

Nimit will play optimal right so wont he always choose 3??
if nimit picks 1 why wont piyush pick 3 , why will he ever pick 2

#2

Hey @bhavik911
Question 1 . Is the numbers given in sorted order??
Answer Nope
Nimit is Greedy , 1 nhi lega

#3

Do i have to do it in O(N) ??

#4

Or Can i just sort it and keep taking the last terms

#5

@bhavik911
Question : Do i have to do it in O(N) ??
Answer Nope

#6

then this??
Or Can i just sort it and keep taking the last terms

#7

@bhavik911
Question : Can i just sort it and keep taking the last terms
Answer Nope

#8

So i should compare 1st and last element at each iteration??

#9

@bhavik911
At first look , this looks like a Greedy problem but it is clearly not so. This can clearly be observed in a simple testcase like
4
5 4 8 6
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.

#10

I dont have much idea about greedy approach
Is it just that we take the max one??

#11

4
5 4 8 6
A/c to greedy approach
Piyush ne 6 liye
Nimit takes 8
ab 4 and 5 hai bs
Piyush takes 5
Nimit takes 4
Piyush ke paas toatal = 6+5
but Actual Answer 13 = 5 + 8

#12

@bhavik911
Question : I dont have much idea about greedy approach
Is it just that we take the max one??
Answer : yes we take the max one

#13

oh ohkay i will look into this