Showing wrong answer for some test cases
@akshitmehta
Going for maximum number on each turn is Greedy Approach while aiming for a maximum total is the Optimal Approach. While the Greedy Approach might work for some testcases , it will not work for all of the them
Try this testcase :
4
2 3 7 4
Using the greedy technque ,
Player 1 picks 4
Player 2 picks 7
Player 1 picks 3
Player 2 picks 2
Player 1 Score = 4 + 3 = 7
Player 2 Score = 7 + 2 = 9
Since our goal was to make sure that Player 1 wins, the greedy technique fails
If we were not inclined to use the greedy technique and had played optimally like this
Player 1 picks 2 (Even though its lesser of 2 & 4)
Player 2 picks 4
Player 1 picks 7
Player 2 picks 3
Player 1 Score = 2 + 7 = 9
Player 2 Score = 4 + 3 = 7
Player 1 wins.
This problem has been discussed in detail in the last video of the Dynamic Programming section with its recursive function and detailed explanation.
Please refer to it.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.