Stop Right There. Are You Dealing Off the Bottom?
Time limit2sMemory limit1024 MB
Given an even deck of cards dealt alternately from the top, find the maximum total sum Jeonghun can collect if he may deal one card from the bottom instead.
- Level
Medium6 of 10
- Topics
- Array, Dynamic programming, Greedy, Prefix sum
- Solved
- No attempts yet
Problem
The air is cold. Jeonghun is playing the following gambling game.
There are N cards and 2 players. The players take turns dealing one card at a time from the top of the deck, to themselves and to the opponent. A player receives the card they deal. When all cards have been dealt, the player whose cards have the larger sum wins. The number of cards is even so that the two players split the cards evenly.
Jeonghun, who is shuffling the cards, is a card sharp. From countless hours of shuffling, he knows every card value after the shuffle. The chance to deal the cards has come to Jeonghun. To win for certain, he decides to deal from the bottom of the deck instead of the top, a move known as bottom dealing. The opponent is famous for being quick to notice, so Jeonghun will bottom deal at most once.
Find the maximum sum of card values Jeonghun can obtain when he bottom deals at most once.
Input
The number of cards N (2 ≤ N ≤ 100,000) is given. N is even.
The second line gives the card values X (1 ≤ X ≤ 10,000) from the top of the deck to the bottom as integers.
Output
Print the maximum sum of card values Jeonghun can obtain.