# 最長遞增子序列
## Longest Increasing Subsequence

----

### 小知識

#### Subsequence 子序列 -> 不用連續
#### Subarray 子串 -> 要連續

---

## [題目敘述](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b032)

給一個長度為 $N$ 的正整數序列 $A$
求最長嚴格遞增子序列長度
即求一序列 $B$ 滿足
$B_1<B_2<B_3 ...<B_k$ ( $k$ 即為答案)
$A_{B_1}<A_{B_2}<A_{B_3}...<A_{B_k}$
>$N<=100$

----

### Sample

A = 9 3 7 4 5 2 6
B = 2 4 5 7 // （位置）不一定是唯一
LIS = 3 4 5 6 // （內容）不一定是唯一
k = 4

---

### 怎麼寫？

按照慣例，設 $dp[i]$ 為由左到右
最後一個位置選 $i$ 的最大長度
最後答案為 $max$ { $dp[i]$ } { $1<=i<=N$ }

----

### 轉移？

$dp[i]=1+max$ { $dp[j]$ } { $j<i$ , $A_j<A_i$ }
簡單來說，就是在滿足
1. 位置在自己前面
2. 數字比自己小

的 $dp[j]$ 中選一個最大的，接在他後面

----

### 實作

#include<iostream>
using namespace std;
const int N=105;
int n,ans,a[105];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];  
        
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            if(a[j]<a[i]){
                dp[i]=max(dp[i],1+dp[j]);
                ans=max(ans,dp[i]);
            }
            
    cout<<ans<<endl;
}

複雜度？ $O(N^2)$

---

## 你以為醬就結束了嗎

----

### [再來一題](https://cses.fi/problemset/task/1145/)

> $N<=2\times10^5$

### 嗨呀！！！

不能 $O(N^2)$ 了怎麼辦？

----

### 直接看做法

1. 維護一個嚴格遞增序列 $X$
2. 從左到右遍歷 $A_i$

if( A[i] > X 中所有元素){
  將 A[i] 放到 X 的最後 // 情況 1 
}
else{
  將 X 中第一個大於等於 A[i] 換成 A[i] // 情況 2 
}

----

### 看個栗子（？

A = 9 3 7 4 5 2 6
-------------------
i=1  A[i]=9
    X是空的 -> 情況 1
    X = 9  // 把 9 放到 Ｘ 的最後
-------------------
i=2  A[i]=3
    3 < 9 -> 情況 2
    X = 3  // 把 9 換成 3
-------------------
i=3  A[i]=7
    7 > 3 -> 情況 1
    X = 3 7  // 把 7 放到 Ｘ 的最後
-------------------
i=4  A[i]=4
    4 < 7 -> 情況 2
    X = 3 4  // 把 7 換成 4
-------------------
i=5  A[i]=5
    5 > 4 -> 情況 1
    X = 3 4 5 // 把 5 放到 Ｘ 的最後
-------------------
i=6  A[i]=2
    2 < 3 -> 情況 2
    X = 2 4 5 // 把 3 換成 2
-------------------
i=7  A[i]=6
    6 > 5 -> 情況 1
    X = 2 4 5 6 // 把 6 放到 Ｘ 的最後

----

### $X$ 能幹嘛

1. $X$ 的長度即為 LIS 的長度
2. $X$ 不是真正的 LIS

剛剛求出的 $X$ 是 2 4 5 6
但真正的 $LIS$ 是 3 4 5 6

----

### 順便一提

$dp[i]$ 就是 $A_i$ 放進 $X$ 的位置

比如說：
$A_i$ 放在 $X$ 中的第 $2$ 個位置， $dp[i]=2$

---

### 另一種做法

其實我們想要找的就是 $max$ { $dp[j]$ } { $j<i$ , $A_j<A_i$ }

因此我們可以用資料結構來維護這個東西
需要的操作有
1. 單點改值
2. 區間求最大值

在由前往後遍歷時，對於每個 $A[i]$ 維護最大的 $dp[i]$
每次要求 $dp[i]$ 時，在 $0$ ~ $A[i]$ 中取 $dp[j]$ 最大值 $+1$ 就可以了

可以用 BIT 或 線段樹 或其他神秘的資結

---

### 怎麼求真正的 LIS

如果有一個 $A_j$ 滿足：
$A_j<A_i$ 和 $dp[j]=dp[i]-1$
那麼 $A_i$ 就可以接在 $A_j$ 的後面

----

### 再來個栗子

A  : 9 3 7 4 5 2 6
dp : 1 1 2 2 3 1 4

對於第 $4$ 個位置， $A_4=4$ , $dp[4]=2$
可以發現 $dp[1]$ 和 $dp[2]$ 都是 $(dp[4]-1)=1$
但只有 $A_2=3$ 比 $A_4=4$ 小
因此在真正的 $LIS$ 中， $A_3$ 就可以接在 $A_2$ 後面

---

## 刷題時間

----

很多 $LIS$ 的題目都是難在看不出他是 $LIS$
只要看出來通常就可以快樂 AC 啦~

----

[2021/1 APCS p4 飛黃騰達](https://zerojudge.tw/ShowProblem?problemid=f608)

[UVa 00481 What Goes Up](https://zerojudge.tw/ShowProblem?problemid=d242)

[2021 TOI 入營考 pC 粉刷護欄](https://tioj.ck.tp.edu.tw/problems/2195)

[UVa 11456 Trainsorting](https://zerojudge.tw/ShowProblem?problemid=d052)