最長遞增子序列(Longest Increasing Subsequence)這個詞，可以分成最長、遞增、子序列三個部分。
子序列(Subsequence)指的是從原本的序列中取出幾項，不一定要連續，但順序不可以改變，因此與上一章節介紹的子數組(Subarray)有些不同，舉例來說「1,5,7」是「1,3,5,7,9」的子序列。
遞增(Increasing)通常是指嚴格遞增，也就是數字依序增加。
而最長就不用特別解釋了，最後整個詞的意思是「原本序列符合數字遞增的子序列中最長的那個」，或者白話一點就是挑出最多的數，讓挑出來的數依序遞增且挑盡量多個數。
如數列「10,22,9,33,21,50,41,60」有LIS「10,22,33,50,60」。而事實上，LIS並不一定是唯一的，如「10,22,33,41,60」也是上述序列的一個LIS。
而接下來開始介紹找出LIS的方法。而由於方法較複雜，因此筆者將其分成兩個部分講解，第一個部分僅能求出LIS的長度，但有部分題目其實只需要這個長度，所以這部份就能解決一些題目了，然後第二個部分是基於第一個部分改進，可以求出一組LIS。兩個部分的複雜度都是O(n log k)，其中n是原始序列的長度，k是LIS長度。
而第一部份的做法呢，我們會需要建立一個輔助的數列，稱作tail，由於這個數列長度會變動，因此建議以vector實作(不熟悉vector可以參考章節1-4)。
最初將tail初始化為空，然後遍歷原數列a，查找a[i]在tail中的lower_bound並更新該元素的值或者新增到tail的尾端。
tail數列的意義有些複雜，tail[i]代表的是所有長度為i+1的「遞增子序列(以下簡稱IS)」中尾端元素的最小值，如果看不太懂沒關係，直接用以下的範例來看。
如果要處理數列：「10,22,9,33,21,50,41,60」，最初tail為空，接著依序開始處理原數列的每個數。
| 遍歷到誰 | tail的值 | 說明 |
|---|---|---|
| 10 | 10 | 10新增到tail尾端，代表目前長度為1的IS的最小的尾端元素是10 |
| 22 | 10,22 | 22新增到tail尾端，代表目前長度為2的IS的最小的尾端元素是22 |
| 9 | 9,22 | 把tail[0]改為9，代表目前長度為1的IS的最小的尾端元素是9 |
| 33 | 9,22,33 | 33新增到tail尾端，代表目前長度為3的IS的最小的尾端元素是33 |
| 21 | 9,21,33 | 把tail[1]改為21，代表目前長度為2的IS的最小的尾端元素是22，也確實能從原數列找到「9,21」 |
| 50 | 9,21,33,50 | 50新增到tail尾端，意義同上 |
| 41 | 9,21,33,41 | 把tail[3]改為41，代表目前長度為4的IS的最小的尾端元素是41，也確實能從原數列找到「9,21,41」 |
| 60 | 9,21,33,41,60 | 60新增到tail尾端，意義同上 |
此時數列遍歷完畢，tail的長度為5，代表存在長度為5的遞增子序列，並且沒有更長的遞增子序列存在，故LIS長度為5。
以下為上面過程的範例程式碼。
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
vector<int> tail;
for(int i=0;i<n;i++){
if(tail.empty()||a[i]>tail.back())tail.push_back(a[i]);
else{
int pos=lower_bound(tail.begin(),tail.end(),a[i])-tail.begin();
tail[pos]=a[i];
}
}
cout<<tail.size(); //輸出結果為LIS長度
}以上的程式碼中，挑出幾個常見的疑點與重點來解釋。
首先lower_bound只是用在排列好的數列，但這邊並沒有sort的出現？
雖然沒有sort的出現，但tail的修改過程可以保證數列一定是排列好的狀態，多嘗試幾組數字就可以發現了。
第二點，在章節1-4提到空的vector使用.back()會導致程式掛掉，為什麼這個程式一開始執行的時候，在tail為空時判斷a[i]>tail.back()不會掛掉？
很多程式語言在執行有邏輯運算的條件判斷時，程式由左而右執行，如果可以直接確定結果，那麼就不會計算剩下的部分，如此處如果tail.empty()成立，那麼因為這個邏輯或運算一定會是1，因此不會執行後面的a[i]>tail.back()，程式也就不會掛掉。在a&&b的情況如果a為0，那麼也不會執行到b，因為可以確定出來的結果會是0。善用這個技巧可以將原本需要分開寫的判斷式整理在一起，十分方便。
而第二部分，要找出一組LIS，需要在以上的程式碼中，紀錄原始數列的每個數被放在tail陣列的哪個位置，也就是以上程式碼的pos。考慮到tail的意義，pos其實代表「這個數可以當作多長的IS的最小尾端」。
所以要找到一組LIS，在知道LIS長度為k後，我們可以從原始數列的尾端開始往回遍歷，假設有一個元素是可以放在長度為k的IS尾端，也就是pos為k-1，那麼就將lis[k-1]設為該元素，接著一直往回跑直到把lis[0]也找到。如果覺得聽起來很抽象，可以看以下範例的過程，同樣是對「10,22,9,33,21,50,41,60」找LIS。
| 遍歷到誰 | 該元素的pos值 | 找到的lis | 說明 |
|---|---|---|---|
| 60 | 4 | ?,?,?,?,60 | 由於60之pos為4，目前也正在找lis[4]，將lis[4]設為60 |
| 41 | 3 | ?,?,?,41,60 | 由於41之pos為3，目前也正在找lis[3]，將lis[3]設為41 |
| 50 | 3 | ?,?,?,41,60 | 50之pos為3，但已經有lis[3]了，因此不用改變 |
| 21 | 1 | ?,?,?,41,60 | 21之pos為1，代表21可以放在長度為2的LIS尾端，但目前在找lis[2]，需要可以放在長度為3的LIS尾端的元素，不能拿21 |
| 33 | 2 | ?,?,33,41,60 | 由於33之pos為2，目前也正在找lis[2]，將lis[2]設為33 |
| 9 | 0 | ?,?,33,41,60 | 9之pos為0，代表9可以放在長度為1的LIS尾端，但目前在找lis[1]，需要可以放在長度為2的LIS尾端的元素，不能拿9 |
| 22 | 1 | ?,22,33,41,60 | 由於22之pos為1，目前也正在找lis[1]，將lis[1]設為22 |
| 10 | 0 | 10,22,33,41,60 | 由於10之pos為0，目前也正在找lis[0]，將lis[0]設為10 |
此時已經找到lis[0]，代表找完了一組正確的LIS，為「10,22,33,41,60」。
以下為上面過程的範例程式碼。
#include<bits/stdc++.h>
using namespace std;
int a[100005],pos[100005],lis[100005];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
vector<int> tail;
for(int i=0;i<n;i++){
if(tail.empty()||a[i]>tail.back()){
pos[i]=tail.size();
tail.push_back(a[i]);
}else{
pos[i]=lower_bound(tail.begin(),tail.end(),a[i])-tail.begin();
tail[pos[i]]=a[i];
}
}
int now=tail.size()-1; //now紀錄目前要找哪一位
for(int i=n-1;i>=0;i--){
if(pos[i]==now){
lis[now]=a[i];
now--;
}
}
for(int i=0;i<tail.size();i++)cout<<lis[i]<<' ';
}有趣的是，以上程式碼找到的LIS也會是字典序最小的，原因可以多想想上面tail、pos等等的定義，並多帶幾組數字試看看。
而LIS除了這個最基本的形式，還有一些不同的變體，例如最長非遞減子序列，也就是把條件中的遞增換成非遞減(Non-decreasing)，所謂的非遞減是指序列的數字後面的要大於等於前面，而原本的遞增只能大於。
至於這個變體的作法其實與原本類似，主要是把push_back(a[i])的時機改成a[i]>=tail.back()，以及插入的位置改成upper_bound()，如此一來能使得出現相同元素時，能優先往後放。
以下為範例程式碼，若輸入原序列為「1 7 5 5」會輸出「1 5 5」。
#include<bits/stdc++.h>
using namespace std;
int a[100005],pos[100005],lnds[100005];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
vector<int> tail;
for(int i=0;i<n;i++){
if(tail.empty()||a[i]>=tail.back()){
pos[i]=tail.size();
tail.push_back(a[i]);
}else{
pos[i]=upper_bound(tail.begin(),tail.end(),a[i])-tail.begin();
tail[pos[i]]=a[i];
}
}
int now=tail.size()-1; //now紀錄目前要找哪一位
for(int i=n-1;i>=0;i--){
if(pos[i]==now){
lnds[now]=a[i];
now--;
}
}
for(int i=0;i<tail.size();i++)cout<<lnds[i]<<' ';
}LIS還有一個非常經典的應用就是解決最長二維遞增的問題(或者常見的稱呼為二維偏序，但偏序的定義相對複雜，所以改以更好理解的名詞稱呼)。
這種問題的形式通常是給定一組二維數據，舉例而言，一組平面上的點，每個點都有自己的(x,y)座標，這就是二維。
然後這個問題的目標，是找出最長的在兩個維度上都能形成遞增的集合，以平面上的點來舉例，就是找出最大的k，使得存在(x1,y1),(x2,y2),...,(xk,yk)滿足x1<x2<...<xk且y1<y2<...<yk。
而另外這類問題給定的原始數據沒有順序的關係，也就是說可以從原始數據中任意挑選元素並進行排列，只要找到最大的集合就好。
而這個問題雖然看似複雜，但其實只要走了關鍵了一步，就可以把問題換成簡單很多的形式。
由於剛才提到這類問題給定的數據沒有順序關係，換句話說我們可以自行重新排序。
因此可以利用sort將數據以第一維進行升序排列，而假設第一維相等的話，則以第二維進行降序排列，這樣一來，只要我們依序選取元素，就能保證第一維至少是非遞減的，此時由於最終的目標是第二維也要遞增，但排好的序列中第二維並沒有特定的順序，因此就可以利用LIS來取出第二維最長的遞增序列，此時我們在第一維相同時對第二維進行降序排列的用處就來了，這種情況下可以保證在取LIS時，當第一維相同時會先取到大的第二維再取到小的，避免出現重複取到相同第一維，如此就能保證第一維會是嚴格遞增了。
而這個問題也還能衍生出一些變體，如2021年1月APCS實作第四題最長二維都非遞減的情況，此時把第一維相同時的排序改成第二維升序，然後改作最長非遞減子序列就好了。
若有回覆需求可以選擇提供email。