tanmay2798's blog

By tanmay2798, history, 3 years ago, In English

Two players are playing a game. They have been given a array of numbers (Array A). Player 1 starts by picking any number.

A player may choose any number adjacent to other player's last pick. If no such number exists, he can choose any number from the remaining unchosen ones. You cannot pick a number which has already been picked by any player.

The two players pick numbers alternatively. Assume both the players play optimally.

The score of a players is the sum of the numbers he has chosen. What is the maximum score Player1 can obtain?

Constraints:

2 <= length of A <= 100000

1 <= A[i] <= 1000

Example:

|A| = 5;

A = {40, 200, 20, 15, 20}

Answer: 240.

Explanation: Player1 chooses 200. Payers2 chooses 40 (among 40 and 20). Player1 chooses 20 (among 20, 15, 20), Player2 chooses 15 (he's only choice). Player1 chooses 20 (last array element).

  • Vote: I like it
  • +4
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

If the size of the array is even then I guess we need to just calculate the alternate position of sum (odd_sum and even_sum) and the answer would be max(odd_sum, even_sum).

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice. I figured that. Do you have any solution for the odd length case?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      Pick the maximum element and now the problem reduces to the even case and solving with respect to the Player 2 with slight modification on the basis of the index of maximum element.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        If the maximum element is at even index (indexing from 1), then there will be 2 sub problems of odd length. Are you suggesting to recursively solve for both?