【競技プログラミング】最長増加部分列を解いてみた【組合せ最適化】

1.初めに

・アルゴリズムを学ぶために、競技プログラミングを始めました。
・AOJのコースをやっていくので、その備忘録を残します。

・前回はナップサック問題を解いたので、今回は「最長増加部分列」を解いていきます。

2.最長増加部分列

2.1問題

数列 $A=a_0,a_1,…,a_{n−1}$ の最長増加部分列 (LIS: Longest Increasing Subsequence) の長さを求めてください。 数列 A の増加部分列は $0≤i_0<i_1<…<i_k<n$ かつ　$a_{i_0}<a_{i_1}<…<a_{i_k}$ を満たす部分列 $a_{i_0},a_{i_1},…,a_{i_k}$ です。最長増加部分列はその中で最も $k$　が大きいものです。

入力

１行目に数列 $A$ の長さを示す整数 $n$ が与えられます。続く $n$ 行で数列の各要素 $a_i$ が与えられます。

出力

最長増加部分列の長さを１行に出力してください。

制約

$1 ≤ n ≤ 100,000$
$0 ≤ a_i ≤ 109$

2.2.最長増加部分列って何？

・問題文を見ても意味がわかんないので、例をあげて考えてみます。

n=5 \\
a_0=5,a_1=1,a_2=3,a_3=2,a_4=4 \\
の時を考えてみる。

a_1=1 < a_3=2 < a_4=4 \\
(i=1<i=3<i=4)\\
or \\
a_1=1 < a_2=3 < a_4=4 \\
(i=1<i=2<i=4)\\

つまり、最大のkは\\
k=3

・みたいな感じでkを求めます。

2.3.DPテーブルを作る

・とりあえず上で使った例でやってきます。

n=5 \\
a_0=5,a_1=1,a_2=3,a_3=2,a_4=4 \\
の時を考えてみる。

増加部分列の長さ(k)	1	2	3	4	5
最終要素の値	inf	inf	inf	inf	inf

・こんなテーブルを考えます。
・数列の最初、$ a_0$から順番に見ていきます。




・$a_0=5$について
　　　　　↓
・5だけで作れる増加部分列は{5}の一つだけ
　　　　　↓

増加部分列の長さ(k)	1	2	3	4	5
最長増加部分列	5	inf	inf	inf	inf

・$a_1=1$について

　　　　　↓
・5、1で作れる増加部分列は{5},{1}の二つ
　　　　　↓
・その中で最長は{5}と{1}
　　　　　↓

増加部分列の長さ(k)	1	2	3	4	5
最終要素の値	5	inf	inf	inf	inf

増加部分列の長さ(k)	1	2	3	4	5
最終要素の値	1	inf	inf	inf	inf

・$ a_2=3$について

　　　　　↓
・5、1、3で作れる増加部分列は{1},{3},{5},{1,3}の四つ
　　　　　↓
・その中で最長は{1,3}
　　　　　↓

増加部分列の長さ(k)	1	2	3	4	5
最終要素の値	1	3	inf	inf	inf

・$ a_3=2$ について

　　　　　↓
・5、1、3、2で作れる増加部分列は{1},{2},{3},{5},{1,2},{1,3}の六つ
　　　　　↓
・その中で最長は{1,2}と{1,3}
　　　　　↓

増加部分列の長さ(k)	1	2	3	4	5
最終要素の値	1	2	inf	inf	inf

増加部分列の長さ(k)	1	2	3	4	5
最終要素の値	1	3	inf	inf	inf

・$ a_4=4$について

　　　　　↓
・5、1、3、2、4で作れる増加部分列は{1},{2},{3},{4},{5},{1,2},{1,3},{1,4},{2,4},{3,4},{1,2,4},{1,3,4}の12個
　　　　　↓
・その中で最長は{1,2,4}と{1,3,4}
　　　　　↓

増加部分列の長さ(k)	1	2	3	4	5
最終要素の値	1	2	4	inf	inf

増加部分列の長さ(k)	1	2	3	4	5
最終要素の値	1	3	4	inf	inf

・と、数列の長さが５だったら自力で何とか求められます。

つまり新しく考える数列の要素「a」について、\\
a'_{k}\leqq a < a'_{k+1}
となるようなa'_{k}を見つけて入れ替える！！

・このような$a'_{k}$は「二分探索」で見つかります。

##2.4.二分探索
・最終要素を小さい方から比べていき、「a」が入るところを見つけると計算量が多くなります(時間がかかる)。
・そこで、二分探索という手法を用いて計算量を減らします。





・みたいな感じです！！！！！

2.4.実装

# 入力値取得
n=int(input())

# dpテーブルの作成
inf=float("inf")
dp=[inf]*n

# 数列の長さの分だけ回す
for i in range(n):

    # 二分探索アルゴリズム
    ok=n
    ng=-1
    a=int(input())
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if dp[mid]>=a:
            ok=mid
        else:
            ng=mid
    dp[ok]=a

for i in range(n):
    if dp[i]==inf: 
        ans=i
        break
else:
    ans=n
print(ans)

参考サイト