これの制約が緩いのが、AtCoderの過去問にあるので、これは理解してるという前提で書きます。

解説

座圧して、数値は $[0, n)$ にあるものとします。

この問題とAtCoderの過去問との唯一の違いが同じ数字を含むというところである。

ある数値が連続するsubsequeceをなんでも取れるというわけではない。

[0, 1, 0, 1, 2]という配列に対して、[0, 0, 1, 2]というのを選ぶことはできない。なぜなら取り損ねた1を選んだsubsequeceの中に入れることができないからだ。

先頭と最後の数値を除き、残りの数値はすべて取らないといけないことが分かる。

ここまでくると後は簡単で、

dp[i][j] := i番目を取るとき、状態がjである。(j == 0 : 先頭要素， j == 1 : 真ん中， j == 2 : 最後)

となるいわゆる耳DPである。真ん中の要素を選ぶときはすべて選ぶように丁寧に遷移しよう。

具体的な遷移は提出コードを参考にしてください(コメントもいれました)

座圧を除いて、計算量は $O(n)$ です。(座圧を含めて、 $O(n \log n)$ です。)

提出コード