I have 2 problems that derive from a simple problem. I'll explain the simple one with the solution I found and after that the modified problem.
Suppose there is a game with 2 players, A and B and a list of positive integers. Player A starts by taking out a number from the list, player B does the same and so on after the there are no longer numbers in the list. Both players sum up the picked numbers. Each player scores the difference between his sum and the opponent's one. The question is what is the maximum score player A can obtain if both players play in an optimal manner.
Now, for this I figured out that the optimal strategy for each player is to take the biggest number at each step.
The following 2 modification:
At the beginning of the game player A should remove K numbers from the list. If he does this in an optimal manner and after that the games is the initial one, what is the maxim score he can obtain?
At each step the players can pick the left-most or the right-most number from the list. Again they play in an optimal manner. Which is the maximum score player A can obtain?
For the second modification I can think of a brute-force approach, i.e. computing the tree of all possibilities, but this does not work for big input data. I believe that there is some kind of DP algorithm.
For the first modification I can't think of an idea.
Can someone help with some ideas for the 2 modifications, what algorithm to design in order to get the response?
For the second variation I found the DP solution at https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/