2142: 拿硬币游戏
Memory Limit：512 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：21
Solved：9
Description
桌上有 n 堆硬币排行一行，n 为偶数。它们的价值分别是 V1，V2，…，Vn，两个玩家轮流从一行硬币堆中取走第一堆或最后一堆，每个玩家都试图最大化自己的总价值。我们需要计算先手能获得的最大价值。
例如： V=｛9，12，7，6} 先手第一次拿 6，对手拿9 先手再拿12，对手拿7后结束。这样先手拿到的最大价值为6+12=18。
Input
第一行一个整数 n。第二行为 n个正整数 V 价值序列。
Output
一个正整数，为先手拿到的最大值。
Sample Input Copy
4
9 12 7 6
Sample Output Copy
18
HINT
n<=10000; Vi<=100000。