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