長さ $N$ の数列 $A$ が与えられる。 数列 $A$ の最長増加部分列のひとつを $B$ とするとき、$\sum B_i$ の最大値を求めよ。
数列 $A$ の最長増加部分列とは、すべての $i < j$ で $A_i < A_j$ を満たす部分列のうち、最長なものを示す。
入力は以下の形式で与えられる。
$N$
$A_1 \dots A_N$
数列 $A$ の最長増加部分列のひとつを $B$ とするとき、$\sum B_i$ の最大値を出力せよ。また、末尾に改行も出力せよ。
4 6 4 7 8
21
最長増加部分列は $ (6, 7, 8)$ と $(4, 7, 8)$ である。よって最大値は $21$ である。
3 1000 2 3
5
最長増加部分列は $(2,3)$ のみである。
7 17 17 13 4 20 12 15
31
7 19 16 14 9 4 20 2
39