最大合計を持つ最長増加部分列
n 個の整数からなる配列が与えられたとき、この配列の最長増加部分列を求めます。複数該当する部分列がある場合は、そのうちどれを出力しても構いません。
配列の部分列とは、残った要素の順序を変えずにいくつか（0 個でも可）の要素を削除することで得られるものです。例えば、配列が の場合、 は の部分列です。しかし、 は要素の順序が変わっているため、 の部分列にはなりません。
💡
配列の増加部分列とは、その要素が昇順になっている部分列を指します。例えば、配列が の場合、 は増加部分列ですが、 は要素が昇順になっていないため、増加部分列ではありません。
入力
入力の最初の行には、配列の長さを示す整数
n (1 ≤ n ≤ 1000) が与えられます。続く 2 行目には、配列の要素となる
n 個の整数 () がスペース区切りで与えられます。出力
最大合計を持つ最長増加部分列の合計を出力してください。
入力 | 出力 |
8
1 3 2 4 5 2 6 5 | 19 |
6
10 9 2 5 3 7 | 14 |
解説
- 最初の例では、合計値が最大となる最長増加部分列は です。
- 2 番目の例では、合計値が最大となる最長増加部分列は です。
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB