C - 数列ゲーム Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君と青木君は長さ 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