最長増加部分列 2 CoffeeScript(Beta)編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
長さ N の数列 A = a_1, ..., a_N が与えられます。
この数列の単調増加な (連続でなくても良い) 部分列の最長の長さを出力してください。
長さ L の数列 B = b_1, b_2, ..., b_L において b_{i-1} < b_i (2 ≤ i ≤ L) が成り立つならば、B は単調増加な数列です。
例えば 1, 2, 3, 4 や 1 は単調増加な数列ですが、4, 3, 2, 1 や 1, 1, 1 は単調増加な数列ではありません。
入力例 1 の場合、 A の単調増加な部分列で長さが最大のものは 1 2 3 4 となります。
(ヒント1)
1 つ前の問題は時間計算量 O(N^2) で解けますが、この問題で同じ解法を用いると実行時間に間に合いません。
O(N^2) 解法でネックとなるのは a_i (1 ≤ i ≤ N) を追加しても単調増加となるような a_j (1 ≤ j ≤ i-1) を O(N) で探していた部分です。
この部分を二分探索を用いて時間計算量 O(log N) に改善することを考えてみてください。
(ヒント2) dp[i] を長さ i の数列の最後の数が取る最小値として考えてみてください。
- 入力される値
-
N
a_1 a_2 ... a_N
・1 行目に数列の長さ N が与えられます。
・2 行目に数列 A の要素 a_1, a_2, ..., a_N が空白区切りで与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
答えを 1 行で出力してください。末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします
・入力はすべて整数
・1 ≦ N ≦ 10^5
・1 ≦ a_i ≦ 10^5 (1 ≦ i ≦ N)
- 入力例1
-
8
1 1 2 2 3 3 4 4
- 出力例1
-
4
- 入力例2
-
9
1 2 1 3 1 4 1 5 1
- 出力例2
-
5
