取数对弈（算法）

取数对弈游戏问题： 取数游戏是一个 2 人对策游戏。游戏开始时将 n 个数在棋盘上从左到右排成一行。 甲乙双方轮流在这一行数的左右两端取数，直至全部取完 n 个数。每人所取得的数的总和为其得分值。 最后双方得分多者获胜。（游戏规定由甲方先取数。） 这里，甲乙双方都采用如下最优策略: 1)甲每次取都希望取到的这个数使自己得分最高 2)乙每次取都希望取到的这个数令甲的得分最低 请编程实现：在甲乙双方都采用最优策略的前提下，计算甲方先取数时双方的最后得分。 输入格式 对于每组输入数据，输入数据的第 1 行有 1 个正整数 n (1<=n<=100)，表示有 n 个数在棋盘上从左到右排成一行。 接下来的 n 个数表示在棋盘上依次排列的 n 个数。 输出格式 在甲乙双方都采用最优策略的前提下，输出计算出的双方的最后得分。甲方得分在前，乙方得分在后。 输入样例 6 4 7 2 9 5 2 输出样例 18 11