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

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

https://qiita.com/kindamu24005/private/3be5a55ce3c6c5275f4d

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

# 2.最長増加部分列


https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_D


## 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.最長増加部分列って何？
・問題文を見ても意味がわかんないので、例をあげて考えてみます。

```math
n=5 \\
a_0=5,a_1=1,a_2=3,a_3=2,a_4=4 \\
の時を考えてみる。
```
![最長部分増加列.001.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/f4b8162e-1906-42ef-2001-341f1d25c8eb.jpeg)
![最長部分増加列.002.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/4c0665f9-ae65-2f2d-4e56-ef95692ada96.jpeg)

```math
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)\\
```

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

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


## 2.3.DPテーブルを作る
・とりあえず上で使った例でやってきます。
```math
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$から順番に見ていきます。
<br>
<br>
・$a_0=5$について
　　　　　↓
・5だけで作れる**増加部分列**は<B>{5}</B>の一つだけ
　　　　　↓
|増加部分列の長さ(k) |1  |2  |3  |4  |5  |
|---|---|---|---|---|---|
|**最長増加部分列**| 5 | inf | inf | inf | inf |
<br>
<br>
・$a_1=1$について

　　　　　↓
・5、1で作れる**増加部分列**は<B>{5}</B>,<B>{1}</B>の二つ
　　　　　↓
・その中で**最長**は<B>{5}</B>と<B>{1}</B>
　　　　　↓
|増加部分列の長さ(k) |1  |2  |3  |4  |5  |
|---|---|---|---|---|---|
|**最終要素の値**| 5 |inf | inf | inf | inf |

|増加部分列の長さ(k) |1  |2  |3  |4  |5  |
|---|---|---|---|---|---|
|**最終要素の値**| 1 |inf | inf | inf | inf |
<br>
<br>
・$ a_2=3$について

　　　　　↓
・5、1、3で作れる**増加部分列**は<B>{1}</B>,<B>{3}</B>,<B>{5}</B>,<B>{1,3}</B>の四つ
　　　　　↓
・その中で**最長**は<B>{1,3}</B>
　　　　　↓
|増加部分列の長さ(k) |1  |2  |3  |4  |5  |
|---|---|---|---|---|---|
|**最終要素の値**| 1 | 3 | inf | inf | inf |
<br>
<br>
・$ a_3=2$ について

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

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

|増加部分列の長さ(k) |1  |2  |3  |4  |5  |
|---|---|---|---|---|---|
|**最終要素の値**| 1 | 3 | inf | inf | inf |
<br>
<br>
・$ a_4=4$について

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

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

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

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

```math
つまり新しく考える数列の要素「a」について、\\
a'_{k}\leqq a < a'_{k+1}
となるようなa'_{k}を見つけて入れ替える！！
```
![最長部分増加列.003.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/94ebfa18-50d7-cbea-4f20-b9f4152e00f6.jpeg)
![最長部分増加列.004.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/ffd2db2f-742e-663f-7899-363398708e67.jpeg)


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

##2.4.二分探索
・最終要素を小さい方から比べていき、「a」が入るところを見つけると計算量が多くなります(時間がかかる)。
・そこで、二分探索という手法を用いて計算量を減らします。
![最長部分増加列.005.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/96e4f33a-5b34-73fa-d1a1-2763460c8345.jpeg)
![最長部分増加列.006.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/d013c298-9208-eb33-3ee5-2c86eafe73ad.jpeg)
![最長部分増加列.007.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/fcb5ad4e-86db-acdc-8710-4dfe02586534.jpeg)
![最長部分増加列.008.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/38e8137c-c0ce-435c-f5d0-55cd95458a5c.jpeg)
![最長部分増加列.009.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/8c3b0419-e877-fe0d-e06d-fb75ffce80af.jpeg)
・みたいな感じです！！！！！

## 2.4.実装
```python
# 入力値取得
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)
```

# 参考サイト

https://qiita.com/python_walker/items/d1e2be789f6e7a0851e5