1250. Stone Game VII

Stones with values are in a row. Alice and Bob alternate turns, starting with Alice, and each turn a player removes either the leftmost or rightmost stone and scores the sum of the remaining stones. Alice maximizes the score difference while Bob minimizes it. Return the difference (Alice's score minus Bob's) under optimal play. The input is JSON {stones}.

Input: JSON {stones}.

Output: Integer — the optimal score difference.

Examples

Input: {"stones":[5,3,1,4,2]}
Output: 6
Explanation: Optimal play leaves a difference of 6.

Input: {"stones":[7,90,5,1,100,10,10,2]}
Output: 122
Explanation: The optimal difference.

Input: {"stones":[1,2]}
Output: 2
Explanation: Alice removes the left stone, scoring the remaining 2; Bob then scores 0.

Constraints

• 2<=n<=1000

Asked by