1933：数字博弈
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：
提交：7
解决：4
题目描述
给定一个数列 $a_1,a_2,...,a_n$，小爱与小艾交替取走一个数字，小爱先取。两人取数时，都只能挑当时数列的首项或末项。取数是必须要完成的动作，不能不取，直到所有的数字都被取走为止。
游戏的目的是看谁拿走的数字之和最大。两人都是非常聪明的，他们都会采用最佳的策略让自己取到的数字之和尽量大。请计算小爱获得的数字之和的最大值。
输入
第一行：单个整数表示 $n$
第二行：$n$ 个整数表示 $a_1,a_2,...,a_n$
$1\le n\le 5000; 0\le a_i\le 10^4$
输出
单个整数，表示先手小爱取走的最大数字之和
样例输入-1 复制
5
10 20 30 40 50样例输出-1 复制
90