How do I maximise the sum in this game?

Question

So, I was asked this question in an interview:

There are two friends playing a game in which they select a number from an array containing n positive numbers. Both friends select one number at a time, and both the players play the game optimally. And you have to find out what's the maximum sum (of numbers that are being selected) that you could obtain after the game ends. The constraints that were given after I gave the answer to the same question without constraints were:

1. On the first move of both players, they can select any number.
2. Apart from first move, they can only select the number which is adjacent to the previous number in the given array and which hasn't been selected by the first and second player up until that moment in the game. (Clarification as edit)

And if a player is not able to make a move, he/she stops playing. And the game ends when both players cannot make a move.

Now, the solution that I gave was:

1. Make a structure containing the value as well as the index of the value in the input array.
2. Make an array of the previous structure and store the values of first step in this array.
3. Sort this array in non-decreasing order on the basis of values.
4. Start selecting a value in a greedy manner and print the maximum value.

They were looking more for a pseudo-code though I can code it too. But, the interviewer said this will fail for some cases. I thought a lot on which cases this will fail but couldn't find any. Therefore, I need help in this question.

Also, if possible, please include a pseudo-code of what I can do to improve this.

Edit: I guess I wasn't clear enough in my question, specifically in 2nd point. What the interviewer meant was:

If it is not the first move of the player, he has to choose a number which is adjacent to one of the number he already selected in previous moves.

Also, yes, both the players play the game optimally and they choose numbers turn by turn.

Edit2: So, the same question was asked from my friend but it was modified a little. Instead of an array, what he was given was a graph. So, like in my case, I can select only the indices that are adjacent to my previously selected indices, what he was given was an undirected graph (adjacency list as input) and he could select only those vertices in a particular move which are directly connected to any of the previously selected vertex.

For eg: Let's say the number of positive integers is 3. The value of those integers are 4, 2, 4 and also, if I name the positive integers by A, B and C, then,

A - B
B - C

The above was the example that my friend was given and the answer to the above would be 6. Can you just point me in the right direction as to how I can begin with this? Thanks!

Answer 1

Given your constraints, the maximum sum in any game will always be the addition of a number of adjacent values, from a given split position S to either position 1 or position N. Player 1 chooses an initial split point S and Player 2 chooses his side of the array to sum (so Player 2 also chooses Player 1's side). One player will add from 1 to S (or S-1) and the other from S (or S+1) to N. The higher sum wins.

In order to win the game, Player 1 must find a split position S such that both addtions from 1 to S-1 and from S+1 to N are strictly smaller than the sum of the other side plus the value of S. This way no matter what side Player 2 chooses to add, its sum will be smaller.

Pseudocode:

1. For each position S from 1 to N, repeat:
1.1. Add values from 1 to S-1 (set to zero if S is 1), assign to S1.
1.2. Add values from S+1 to N (set to zero if S is N), assign to SN.
1.3. If S1 is smaller than S+SN and SN is smaller than S+S1, then S is the winning position for Player 1. If not, repeat.
2. If you have found no winning position, then whatever you choose Player 2 can win choosing in turn an optimal position.

Answer 2

To complete @Ivlad's anwser, there exists a strategy for which p1 will never lose (there may be a draw in the worst case). She can always find a x such that the sum she obtains is not smaller than p2's sum.

The proof goes as follows -- sorry this more math that coding. I consider an array of positive numbers (up to a constant translation, there is no loss of generality here).

I denote a = [a[0],...,a[n]] the array under consideration and for any k<=l, S[k,l] = a[k]+...+a[l] the sum of all terms form rank k to rank l. By convention, S[k,l]=0 if k>l.

As explained in previous comments, picking up a[k+1] guarantees p1 to win if:

a[k+1] >= max( S[1,k]-S[k+2,n] , S[k+2,n]-S[1,k] )

Let consider D[k] = S[1,k] - S[k+1,n], the difference between the sum of the first k terms and the sum of other terms. The sequence D is decreasing, negative for k=0 and positive for k=n. We can an index i such that:

D[i] <= 0
D[i+1] => 0

(in fact, one of the two above inequalities must be strict).

Substituting for S and noticing that S[1,k+1]=S[1,k] + a[k+1] and S[k+1,n]=S[k+2,n] + a[k+1], the two inequalities in D imply:

S[1,i] <= S[i+2,n] + a[i+1]
S[1,i] + a[i+1] >= S[i+2,n]

or equivalently:

a[i+1] >= S[1,i] - S[i+2,n]
a[i+1] >= S[i+2,n] - S[1,i]

In other words, choosing a[i+1] is strategy with which p1 cannot lose.

In fact, this strategy offers the largest payoff for p1. Note that it is not unique even if all terms of the array are strictly positive. Consider for example a=[1,2,3], where p1 can indifferently choose 2 or 3.

Answer 3

As the OP mentioned that both player play the game optimally,I am going to present an algorithm under this assumption.

Definitely if both players play optimally,then definitely the sum they obtain at the end would be maximum,otherwise they are not playing optimally.

There are two different cases here:

I make the first move and pick element at position x

Now because we have to obey the condition that only adjacent elements could be picked,let me define two arrays here.

left[x]: It is the sum of elements that can be obtained by adding

array[0],array[1]....array[x-1],the elements left to x.

right[x]: It is the sum of elements that can be obtained by adding

array[x+1],array[x+2]....array[n-1],the elements right to x.

Now,because the other player also plays optimally,what he will do is he will check what I can possibly achieve and he finds that,I could achieve the following:

array[x] + left[x] = S1

OR

array[x] + right[x] = S2

So what the other player does is finds the minimum of the S1 and S2.

If S1 < S2 this means that if the other player picks element at x+1,he just took away the better part of array from us because now we are left with a lesser sum S1

If S1 > S2 this means that if the other player picks element at x-1,he just took away the better part of array from us because now we are left with a lesser sum S2

Because I am also playing optimally I would in the very first move pick such x which has minimum absolute value of (right[x]-left[x]),so that even if our opponent takes the better part of array from us,he is only able to take away minimum

Therefore,If both players play optimally, the maximum sums obtained are:

Update.

x + left[x]  and right[x]//when second player in his first move picks x+1

Therefore,in this case the moves made are:

Player 1:Picks element at position x,x-1,x-2....0.

Player 2:Picks element at position x+1,x+2,....n-1

Because each player has to pick adjacent element to the previously picked element by him.

OR

x + right[x] and left[x]//when second player in his first move picks x-1

Therefore,in this case the moves made are:

Player 1:Picks element at position x,x+1,x+2....n-1.

Player 2:Picks element at position x-1,x-2,....0.

Because each player has to pick adjacent element to the previously picked element by him.

where x is such that we obtain minimum absolute value of (right[x]-left[x]).

Since OP insisted on posting pseudocode,here is one:

Computing the left and right array.

for(i = 0 to n-1)
{
 if(i==0)
  left[i]=0;
 else left[i] = left[i] + array[i-1];

 j = n-1-i;
 if(j==n-1)
  right[j]=0;
 else right[j]= right[j] + array[j+1];
}

The left and right arrays initially have 0 in all positions.

Computing max_sums.

Find_the_max_sums()
{
 min = absoulte_value_of(right[0]-left[0])
 x = 0;
 for(i = 1 to n-1)
 {
  if( absolute_value_of(right[i]-left[i]) < min)
  {
   min = absolute_value_of(right[i]-left[i]); 
   x=i;
  }
 }
}

Clearly Both space and time complexity of this algorithm is linear.

Answer 4

Notice that if you make the first move at index x, if your opponent plays optimally, their first move will have to be at index x-1 or x+1. Otherwise, they will have elements that they could have picked but didn't. To see this, consider two non-adjacent starting points:

-------y-------------x-------

Eventually they will both take elements from the array and end up with something like:

yyyyyyyyyyyyyyxxxxxxxxxxxxxxx

So you can relocate the starting points to the middle yx, obtaining the same solution.

So, assume you move first at x. Let:

s_left_x = a[0] + ... + a[x]
s_right_x = a[x] + ... a[n - 1]

s_left_y = a[0] + ... + a[x - 1]
s_right_y = a[x + 1] + ... + a[n - 1]

Let's say you want to win the game: have a larger sum than your opponent at the end. If your opponent picks x + 1, you want s_left_x > s_right_y, and if your opponent picks x - 1, you want s_right_x > s_left_y. This is ideally, in order to win. It's not always possible to win though, and your question doesn't ask how to win, but rather how to get the largest sum.

Since your opponent will play optimally, he will force you into the worst case. So for each x as your first move, the best you can do is min(s_left_x, s_right_x). Pick the maximum of this expression for each index x, which you can find in O(1) for each index after some precomputations.

Answer 5

Ok, I think this is solution, that is formulated more briefly:

1st player must pick the item that bisects the array in a way two resulting arrays' sums difference is less, than picked item's value.

If it's achievable, p1 wins, if not, p2 wins.

Obviously, on his 1st move p2 must choose the item next to p1's, as it is the only way for him to get maximum sum. He chooses the item on the side, where the sum of remaining items is bigger. This will be the maximum sum p2 can get also.

p1's maximum sum will be the sum of remaining items (items that are on the side, that p2 has not chosen plus item p1 picked in first move).