最長増加部分列 2
整数が
n 個並んだ配列が与えられるとき、その配列の最長増加部分列を求める問題です。最長増加部分列が複数存在する場合は、いずれかひとつを出力すればかまいません。配列の部分列 (subsequence) は、配列からいくつかの要素を削除して残った要素の順番を変えずに得られる列のことです。たとえば、配列 があるとき、 は の部分列ですが、 は残った要素の順序が変わってしまうため部分列ではありません。
💡
増加部分列とは、部分列の要素が昇順になっているものを指します。たとえば、配列 に対して、 は増加部分列ですが、 は要素が昇順になっていないため増加部分列ではありません。
入力
最初の行には、配列の長さを表す整数
n (1 ≤ n ≤ 100 000) が与えられます。2 行目には、配列の要素として
n 個の整数 () がスペース区切りで与えられます。出力
配列の最長増加部分列の長さを出力してください。
例
Input | Output |
8
1 3 2 4 5 2 6 5 | 5 |
6
10 9 2 5 3 7 | 3 |
解説
- 最初の例では、配列の最長増加部分列のひとつとして が挙げられます。
- 2 番目の例では、 が最長増加部分列のひとつです。
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB