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

Auto comment: topic has been updated by tanmay2798 (previous revision, new revision, compare).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).

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

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.

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?

Yes, however going by constraint, you'll have to use dp.

I thought of this, but instead of choosing the highest value element, I thought I would have to choose every element and recur on both sub parts.

Can you explain why you think this greedy choice will work here?

for the full solution i think we need to calculate it for each suffix and prefix.