Maximize the sum of chosen numbers 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?


and


  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?

[LATTER EDIT]

For the second variation I found the DP solution at https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/
Here is the post for the 2nd modification, which is

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?

The solution is based on DP. For the sub-problem (i-j) i.e. v[]i, v[i+1], ..., v[j] there are two choices:

The user chooses the i-th element with value v[i]: The opponent either chooses (i+1)-th element or j-th element. The opponent intends to choose the element which leaves the user with minimum value. i.e. The user can collect the value v[i] + min(F(i+2, j), F(i+1, j-1))



The user chooses the j-th element with value v[j]: The opponent either chooses i-th element or (j-1)-th element. The opponent intends to choose the element which leaves the user with minimum value.
i.e. The user can collect the value v[j] + min(F(i+1, j-1), F(i, j-2))


Following is recursive solution that is based on above two choices. We take the maximum of two choices.

F(i, j) represents the maximum value the user can collect from i-th coin to j-th coin.
F(i, j) = Max(v[i] + min(F(i+2, j), F(i+1, j-1)), v[j] + min(F(i+1, j-1), F(i, j-2)))
Base Cases
F(i, j)  = v[i] If j == i
F(i, j)  = max(v[i], v[j])  If j == i+1

Here is a pice of code in Python that solves it
def optimalStrategyOfGame(arr, n): 
  
    # Create a table to store solutions of subproblems  
    table = [[0 for i in range(n)] for i in range(n)] 

    # Fill table using above recursive formula. Note that the table is  
    # filled in diagonal fashion from diagonal elements to table[0][n-1] which is the result.  
    for gap in range(n): 
        for j in range(gap, n): 
            i = j - gap 
          
            # Here x is value of F(i+2, j), y is F(i+1, j-1) and z is  
            # F(i, j-2) in above recursive formula  
            x = 0
            if((i + 2) &lt;= j): 
                x = table[i + 2][j] 
            y = 0
            if((i + 1) &lt;= (j - 1)): 
                y = table[i + 1][j - 1] 
            z = 0
            if(i &lt;= (j - 2)): 
                z = table[i][j - 2] 
            table[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z)) 
    return table[0][n - 1] 

[SOURCE] https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/