← 返回题目列表

AtCoder · abc031_c

C. 数字序列游戏

中文机器翻译题面 查看原题

問題文

高桥君和青木君长 N 序列 使用 S 玩游戏。

比赛轮到高桥和青木了。 由 1 次组成。

游戏玩法如下。

  • 首先,高桥君出了序列的元素 圈 1 。
  • 接下来,青木先生选择了高桥先生没有圈出的序列元素。 1 。
  • 高桥君和青木君标记了圆圈。 2 对于每个元素,其 2 删除除一个元素之外的所有元素以及它们之间的所有元素。剩余的数列 将其设置为 T 。
  • 数列 T 的序列 T 左边奇数元素的总和是高桥的分数,偶数元素的总和是青木的分数。

在可以圈出的元素中,青木会圈出他可以获得最多分数的元素。如果有多个这样的元素,请圈出其中最左边的元素。

高桥君知道如何标记青木君的圆圈。求高桥可以获得的最大可能分数。


入力

输入是按以下格式从标准输入给出的。

N
a_1 a_2 ... a_N
  • 1 行包含一个整数 N (2≦N≦50) 。 表示N 是一个数字序列 它是 S 中的元素数量。
  • 2 行中,N 整数 给出了 a_1, a_2, ... , a_N (-50≦a_i≦50, 1≦i≦N) 。整数 从 a_i 是一个数字序列 它是 S 左侧开始 表示第 i 个元素。

出力

高桥可以获得的最高分数是 1 行输出。

还在输出末尾包含换行符。


入力例1

6
1 -3 3 9 1 6

出力例1

6

高桥左起 最好选择第 2 个元素。在这种情况下,青木君在左边。 选择第 5 个元素,以及结果序列 T 从左到右 -3, 3, 9, 1 变为。高桥君 青木君的 6 得分 您可以获得 4 积分。


入力例2

3
5 5 5

出力例2

10

对于青木来说,无论选择哪个元素,可以获得的积分为 5 仍然成立,但如果有多个选择可以最大化得分,那么高桥的得分是 10 。


入力例3

8
-1 10 -1 2 -1 10 -1 0

出力例3

-1