一.最長上升子序列（LIS）的相關知識

1.最長上升子序列（Longest? Increasing Subsequence），簡稱LIS，也有些情況求的是最長非降序子序列，二者區別就是序列中是否可以有相等的數。假設我們有一個序列 b i，當b1 < b2 < … < bS的時候，我們稱這個序列是上升的。

（或許我們剛開始對于這樣的名詞感到陌生，對于解釋也不理解，那我們就要知道它的前置知識）

?一.什么是子序列？

? ? 一個序列A={a1,a2,...an}中任意刪除若干項，剩余的序列叫做A的一個子序列。例如序列A={1,3,5,4,2}，刪除其中的第3項和第5項，得到序列B={1,3,4}，刪除其中的第3項和第4項，得到序列C={1，3，2}，此時序列B和C是序列A的子序列。

二.什么是最長子序列？

? ? 如果序列中的元素是從小到大排列的，則該序列為上升序列，如果該序列又是其它序列的子序列，則稱為上升子序列。例如“1.1 子序列”中提到的B是A的上升子序列，而C是A的子序列，但不是上升子序列。

了解這兩個前置知識，那么最長上升子序列就很容易理解了。

即包含元素最多的上升子序列，叫做最長上升子序列。

?

?二.LIS長度的求解方法

一.方法一：動態規劃（O(n^2)樸素法）

動態規劃的一個特點就是當前解可以由上一個階段的解推出， 由此，把我們要求的問題簡化成一個更小的子問題。我們求最長上升子序列也符合這一特點，我們要求前n個數的最長上升子序列就是可以轉換成求前n-1個數的最長上升子序列......這樣逐步分解，直到求前1個數的最長上升子序列。

狀態轉移方程為：dp[i]=max(dp[i],dp[j]+1)

其核心代碼段為：

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

---

?

二.方法二：貪心+二分（O(nlogn)）

用一個low數組記錄長度，low[i]表示長度都為i的LIS結尾元素的最小值，這樣我們在記錄low的時候，當a[i]大于low[++當前LIS最大長度]時候，直接將a[i]接在low中，否則在low中二分查找大于等于當前元素a[i]的第一個位置pos，用a[i]替換掉之前的low[pos].最后我們找一下最長上升子序列下標滿足的解，記錄下該子序列即可.(注意，low數組不一定是最長上升子序列，只是長度對等)

這里的二分操作可以用STL中的lower_bound（）函數實現。

核心代碼段：

low[++sum]=a[1];
for (int i = 2; i <= n; i++) {if (a[i] > low[sum])low[++sum] = a[i];else{int k = lower_bound(low + 1, low + sum + 1, a[i]) - dp;low[k] = a[i];}
}

?

三.例題分析

?一.B3637 最長上升子序列

?

?這一題就相當于最長上升子序列的模版題，通過動態規劃（樸素法）就可以解決，這里可以當做模版學習。

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
int dp[N], a[N];
int ans, n, m, sum;
int main()
{cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];dp[i] = 1;           //初始化，dp都為1，即自身是一個上升子序列}for (int i = 1; i <= n; i++) {for (int j = 1; j < i; j++) {  //如果在之前的序列有小于a[i]的，更新dpif (a[i] > a[j])dp[i] = max(dp[i], dp[j] + 1);}}for (int i = 1; i <= n; i++) {ans = max(ans, dp[i]);   //找出最長的上升子序列}cout << ans << endl;return 0;
}

二.LIS

這一題和剛剛的題目的意思是一模一樣的，唯一的區別就是數據范圍變大了，變為1e5，如果我們還是和剛剛一樣使用O(n^2)的方法，肯定會超時，那么我們就應該使用方法二：貪心+二分? ? ? ?（O（nlogn））

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int a[N], b[N];
int n, m, sum, ans;
int main()
{cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}b[++sum] = a[1];     //核心代碼段，沒什么好說的for (int i = 2; i <= n; i++) {if (a[i] > b[sum])b[++sum] = a[i];else{int k = lower_bound(b + 1, b + sum + 1, a[i]) - b;b[k] = a[i];}}cout << sum << endl;return 0;
}

這里給大家留下兩道練習題，這兩道題都是在此基礎上的變形題，可以會有點難（都是洛谷上的題，可以看題解），后面我也會給出分析。

[ARC149B] Two LIS Sum

P8736 [藍橋杯 2020 國 B] 游園安排

另外，關于LIS還有一個姊妹叫作LCS（最長公共上上子序列），下次我們將講解相關內容，好了今天的內容就到這里了。~QVQ~