Maximize the difference of the sum of picked numbers by 2 players

Question

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. The goal for each player is to maximize the difference between his sum and opponent's sum, which is the score. 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 pseudocode is the following:

sumA = 0
sumB = 0
list = [1, 5, 3, 7, 9]

while list IS NOT EMPTY:
    val = pop_max(list)
    sumA = sumA + val

    if list IS NOT EMPTY:
        val = pop_max(list)
        sumB = sumB + val


scoreA = sumA - sumB
print scoreA

This can run in O(n) or O(n*log(n)) depending how the numbers from list are sorted.

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 algorithm ideas for the 2 modifications?

[LATTER EDIT]

The solution for the 2nd modification can be found here https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/ It is DP.

Answer 1

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:

1. 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))

2. 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) <= j): 
                x = table[i + 2][j] 
            y = 0
            if((i + 1) <= (j - 1)): 
                y = table[i + 1][j - 1] 
            z = 0
            if(i <= (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/