最長増加部分列 2 Python3編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
長さ N の数列 A = a_1, a_2, ..., a_N が与えられます。
この数列の (連続でなくても良い) 部分列で、公比 が 2 である等比数列の最長の長さを出力してください。
長さ L の数列 B = b_1, b_2, ..., b_L において b_i = 2 × b_{i-1} (2 ≤ i ≤ L) が成り立つならば、B は公比 が 2 の等比数列です。
例えば 2, 4, 8 や 11 は公比 が 2 である等比数列ですが、4, 3, 2, 1 や 1, 1, 1 や 2, 6, 18 は公比 が 2 である等比数列ではありません。
- 入力される値
-
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 ≦ 9×10^15 (1 ≦ i ≦ N)
- 入力例1
-
8
1 1 2 2 3 3 4 4
- 出力例1
-
3
- 入力例2
-
9
1 2 1 3 1 4 1 5 1
- 出力例2
-
3
