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