公式解説ではDPの解説でしたが、ここではDPを使用しない解法を紹介します。

\(N\)が偶数の時は数列の末尾に十分小さい負数を挿入することで \(N\)が奇数の場合に帰着できます。 以下\(N\)が奇数とします。

選ぶ個数を\(M\)とします。\(2×M+1=N\)です。

数列\(A\)の具体例として、\(0,1,2,3,4,5,6\)を使って説明します。 \(A\)の0indexで奇数番目を選んだ状態を基準状態と呼びます。

例でいうと、\(0,①,2,③,4,⑤,6\)　が基準状態です。

あり得るすべての選び方は、基準状態から、選ばれたM個の要素のうち、左から\(i(0≦i≦M)\)個の要素の選択を1つ左にずらし、右から\(j(0≦j≦M,i+j≦M)\)個の要素の選択を1つ右にずらしたものとなっています。例えば、\(⓪,1,2,③,4,5,⑥\)は\(i=j=1\)の時です。

左からi個ずらした時の合計の増分と、右からj個ずらした時の合計の増分はそれぞれ\(O(N)\)で計算できます。例でいうと\([0,-1,-2,-3]\)と、\([0,1,2,3]\)です。

jを固定した時に選べるiの範囲は\(0\)から\(M-j\)までの範囲なので、この範囲の最大値は累積最大値をあらかじめ求めておくことで\(O(1)\)で求められます。

よって、\(i,j\)を動かした時の基準状態からの合計の増分の最大値が\(O(N)\)で求められたので、この問題が\(O(N)\)で解けました。

実装例(python)