Maximize the sum of chosen numbers

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. 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/

Answer 1

The first modification can be solved with dynamic programming.

In the original problem, given N numbers $x_1$ to $x_N$, the optimal strategy for both sides is to always take the largest number (this is not trivial to prove, but not difficult either). Since there is no restriction which number to pick we may assume $x_1 ≥ x_2 ≥ ... ≥ x_N$.

Now let f(k, n) be the optimal score that can be achieved if we use the first n numbers only, and remove k of those in an optimal way (k ≤ n). We are therefore looking for f(K, N). f(0, n) is easily calculated by adding and subtracting $x_i$ in turn.

If we look for f(k, n), k ≥ 1: If k = n then we remove all of the first n numbers, so f(k, n) = 0. If k < n: We take the first n numbers, then remove k of those. Either we remove k of the first n-1 numbers and keep $x_n$, or we remove k-1 of the first n-1 numbers, then remove $x_n$, and we pick whatever is better.

In the first case, the score is f(k, n-1) and then we add or subtract $x_n$, depending on whether n-k is even or odd. The score is f(k, n-1) + $x_n$ if n-k is odd, and f(k, n-1) - $x_n$ if n-k is even.

In the second case, since $x_n$ is removed, the score is f(k, n) = f(k-1, n-1). All in all:

If n-k is odd then f(k, n) = max(f(k, n-1) + $x_n$, f(k-1, n-1)). If n-k is even then f(k, n) = max(f(k, n-1) - $x_n$, f(k-1, n-1)). And the final result is f(K, N).

If we change it to "remove up to K numbers" then the result is the largest of f(i, N) for 0 ≤ i ≤ K.

Answer 2

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/