什么是「上升子序列」

给一串数 $a_1,a_2,\dots,a_n$ ，子序列是从中挑出若干个数、保持原来的先后次序（但不必相邻）得到的序列；若挑出的这串数严格递增，就是一条上升子序列。我们要找的，是其中最长的一条——它的长度就是 LIS （Longest Increasing Subsequence）。

序列 2 1 5 3 6 4 8 9 7：柱高即数值。高亮的 1→3→6→8→9 是一条长度 5 的上升子序列——下标递增、数值也递增。

盯住上图： $1,3,6,8,9$ 这五个数在原序列里的下标是 $1<3<4<6<7$ （递增，说明保持了原次序），对应的数值 $1<3<6<8<9$ 也递增——两个条件都满足，是合法的上升子序列。能不能更长？试遍所有挑法，答案是不能，所以这题的 LIS 长度是 5。

那能不能贪心，从左到右「能接就接」？看这条链就会翻车：从 2 起步，遇到 5 接上（2,5），再遇 6 接上（2,5,6），往后 8、9 也接，得到 2,5,6,8,9——长度也是 5，碰巧不差。但若序列是 $1,100,2,3,4$ ，贪心从 1 接了 100 就卡死（后面再没有比 100 大的），只得长度 2；而正解是 $1,2,3,4$ 长度 4。此刻接哪个数最好，取决于后面还有什么——这正是需要 DP 的信号。

要枚举所有子序列？那是 $2^n$ 种挑法， $n=1000$ 就已无从枚举。下面用 DP 把它压成 $O(n^2)$ ，再进一步压到 $O(n\log n)$ 。

状态与转移：以某个数「结尾」

难点在于「子序列可以在任意位置结尾」，直接对整体设状态很滑。换个抓手：强制枚举它以哪个数结尾。设 $dp[i]$ 表示：以 $a_i$ 为最后一个元素的最长上升子序列的长度。这样每条上升子序列都被它的结尾唯一「认领」，不重不漏。

算 dp（以 9 结尾）：向左看每个比 9 小的数，谁的 dp 最大就接在谁后面，再 +1。这里 6 的 dp=3 最大，故 dp=3+1=4。

怎么算 $dp[i]$ ？既然它以 $a_i$ 结尾，那 $a_i$ 前面那个数 $a_j$ 必须满足两件事：下标更靠前（ $j<i$ ）、数值更小（ $a_j<a_i$ ，才「上升」）。在所有这样的 $j$ 里，谁结尾的子序列最长（ $dp[j]$ 最大），就把 $a_i$ 接到它后面，长度 $+1$ ：

dp[i]=1+\max_{\,j<i,\ a_j<a_i}dp[j]

如果左边没有任何更小的数可接，这个 $\max$ 为空， $dp[i]$ 就取初值 1（ $a_i$ 自己单独成一条长度 1 的串）。最终答案不是 $dp[n]$ ——因为 LIS 可以在任何位置收尾——而是整个 dp 数组的最大值：

\text{LIS}=\max_{1\le i\le n}dp[i]

本质

「以 $a_i$ 结尾」这个限定，把「求全局最长」拆成了 $n$ 个彼此独立、可按下标顺序递推的小问题。每个 $dp[i]$ 只依赖它左边已算好的 $dp[j]$ ，于是 $2^n$ 种挑法被 $O(n^2)$ 次比较装下。★答案取全行最大，别顺手写成 $dp[n]$ 。

跟着算一遍

用序列 $a=[2,1,5,3,6]$ 走几步（下标从 1 记），把方程跑起来：

1

前两个数。

dp[1]=1

（2 自成一串）；到 1 时，左边只有 2，而

2<1

不成立，接不上 →

dp[2]=1

。

2

第 3 个数 5。 左边

2<5

、

1<5

都能接，取

\max(dp[1],dp[2])+1=\max(1,1)+1=2

→

dp[3]=2

（如 2,5）。

3

第 4 个数 3。 能接的是

2<3

、

1<3

（

5<3

不行），

\max(dp[1],dp[2])+1=2

→

dp[4]=2

（如 2,3）。

4

第 5 个数 6。 左边全比它小，来源里

dp[3]=2

（结尾 5）与

dp[4]=2

（结尾 3）最大，

2+1=3

→

dp[5]=3

。当前全行最大是 3（如 2,5,6 或 2,3,6）。

下面的演示把

dp[]

逐格填出来，并高亮每个

dp[i]

向左扫描时「能接 / 跳过 / 采纳」的来源。改数组、加删元素，或换个预设看它实时重算。

看它一格一格长出来

当前数组的最长上升子序列长度：LIS = 5 （= dp[] 全行最大值，可在任意位置结尾）

0

1

2

3

4

5

6

7

8

a

dp

2

1

5

3

6

4

8

9

7

·

当前计算依赖来源被选转移已确定

dp[i]=1\ \ (\text{init, each element alone})

上排是原数组 a[]（只读参照），下排 dp[i] 表示「以 a[i] 结尾的最长上升子序列长度」。每个 dp[i] 至少是 1（数字自己就是长度 1 的串），再看左边有没有更矮的数能接在它前面。

进度

已暂停，第 1 步，共 56 步，1 倍速

深化：O(n log n) 贪心 + 二分

$O(n^2)$ 应付 $n\le 5000$ 绰绰有余，但 $n=10^5$ 就会超时。瓶颈在那句「向左扫所有 $j$ 」。能不能不扫？关键洞察是一个贪心：要让子序列有机会更长，同样长度的上升子序列，它的结尾越小越好——结尾越小，后面越容易接上更多数。

于是维护一个数组 $tails$ ： $tails[k]$ 表示所有长度为 $k{+}1$ 的上升子序列中，最小的那个结尾。它有个漂亮性质—— $tails$ 本身严格递增（长度越长，最小结尾必然越大）。逐个处理 $a_i$ ：

两种动作：① 当前数比 tails 末尾大 → 追加到末尾，LIS 长度 +1；② 否则二分找第一个 ≥ 它的位置，替换掉——把那个长度的结尾压得更小。

动作一 · 追加。若 $a_i$ 比 $tails$ 当前末尾还大，它能接在最长那条的后面，于是把它追加到 $tails$ 末尾——LIS 长度增长 1。

动作二 · 替换。否则，用二分在 $tails$ 里找第一个 $\ge a_i$ 的位置（ $\texttt{lower\_bound}$ ），把那一格替换成 $a_i$ 。含义是：某个长度的子序列，如今找到了一个更小的结尾，长度没变，但为后面接续腾出了更多空间。

因为 $tails$ 始终有序，二分只需 $O(\log n)$ ，总复杂度降到 $O(n\log n)$ 。最终 $tails$ 的长度就是 LIS。要当心一个常见误解： $tails$ 的内容不一定是某条真实存在的上升子序列（它是被反复替换出来的），但它的长度恒等于 LIS，这才是我们要的答案。

下面的动画把耐心排序逐元素放慢：看每个数如何二分命中

tails

的某一格——追加（末尾长出新格）还是替换（某格数字被压小）。同一个「经典乱序」，最终

tails

长度依旧是 5，和上面

O(n^2)

的答案完全一致。

逐个扫描输入序列 a[]，每个数用二分决定它在 tails 里的落点已扫 0/9

215364897

tails —— tails[k] 记「长度 k+1 的上升子序列的最小结尾」长度 = LIS = 0

0

·

点播放或 下一步 开始。tails 从空开始，逐个把 a[] 里的数二分安放进去；它的长度随追加而增长，最终就是 LIS 长度。

进度

已暂停，第 1 步，共 10 步，1 倍速

常见陷阱 · 严格上升 vs 不降

求严格上升子序列，二分用 $\texttt{lower\_bound}$ （第一个 $\ge a_i$ ，相等也替换）；若改求不降（允许相等）子序列，则要换成 $\texttt{upper\_bound}$ （第一个 $> a_i$ ）。一字之差，结果就差一截——下一节 LCS 里 P1439 排列 LCS 正是靠把问题转成 LIS、再用这套二分做到 $O(n\log n)$ 的。

例题

B3637最长上升子序列洛谷原生普及-

题意

给定长度

n

的序列，求其最长严格上升子序列的长度。

为什么选它

最裸的 LIS 模板，

n\le 5000

正好让

O(n^2)

双层循环通过——拿来把「以

a_i

结尾 + 全行取最大」这套状态设计写熟，一行不多一行不少。

转移 · 复杂度

dp[i]=1+\max_{j<i,\,a_j<a_i}dp[j]

，答案

\max_i dp[i]

；时间

O(n^2)

。

参考代码（O(n²) 裸模板）

C++

在洛谷打开 B3637

#include <algorithm>
#include <iostream>
using namespace std;

int n, ans, a[5005], dp[5005];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++)
    {
        dp[i] = 1;                      // 每个数自成长度 1 的上升串
        for (int j = 1; j < i; j++)     // 向左看能接在谁后面
        {
            if (a[j] < a[i])            // 严格上升才能接
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);          // ★LIS 可在任意位置结尾，取全局最大
    }

    cout << ans << endl;
    return 0;
}
// TAG: 线性DP LIS 最长上升子序列

P1020[NOIP1999 提高组] 导弹拦截NOIP1999 提高提高+/省选-

题意

一套拦截系统首发不限高度，此后每发不能高于前一发。给出依次飞来的导弹高度，求：① 一套系统最多拦几发；② 最少几套系统才能全拦。

对应关系

① = 最长不升子序列长度；② 由 Dilworth 定理，「最少用几条不升子序列覆盖整个序列」等于「最长上升子序列长度」。

为什么选它

n

可达十万级，

O(n^2)

会 T——逼你上 $O(n\log n)$ 二分。同时它把「不升」和「上升」两种变体、以及 Dilworth 这条经典结论一次讲透，是 LIS 进阶第一题。

转移 · 复杂度

两个单调栈

g1

（不升）、

g2

（上升）各做一遍二分替换；时间

O(n\log n)

。

参考代码（O(n log n) 二分 + Dilworth）

C++

在洛谷打开 P1020

#include <algorithm>
#include <iostream>
using namespace std;

int n, a[100005];
int g1[100005], len1;            // 第一问：最长不升子序列的「结尾」栈
int g2[100005], len2;            // 第二问：最长上升子序列的「结尾」栈

int main()
{
    while (cin >> a[++n]);           // 读到文件尾，n 会多算 1
    n--;

    for (int i = 1; i <= n; i++)
    {
        // 第一问：一套系统能拦的最多导弹 = 最长「不升」子序列长度。
        // 维护一个「各长度的最大结尾」序列 g1（单调不升），二分找第一个 < a[i] 的位置替换。
        if (len1 == 0 || g1[len1] >= a[i])
        {
            g1[++len1] = a[i];
        }
        else
        {
            int l = 1, r = len1;
            while (l <= r)                       // 找第一个 g1[p] < a[i]
            {
                int mid = (l + r) >> 1;
                g1[mid] < a[i] ? r = mid - 1 : l = mid + 1;
            }
            g1[l] = a[i];
        }

        // 第二问（Dilworth）：最少拦截系统数 = 最长「上升」子序列长度。
        // g2 单调上升，二分找第一个 >= a[i] 的位置替换（lower_bound）。
        if (len2 == 0 || g2[len2] < a[i])
        {
            g2[++len2] = a[i];
        }
        else
        {
            int l = 1, r = len2;
            while (l <= r)                       // 找第一个 g2[p] >= a[i]
            {
                int mid = (l + r) >> 1;
                g2[mid] >= a[i] ? r = mid - 1 : l = mid + 1;
            }
            g2[l] = a[i];
        }
    }

    cout << len1 << endl << len2 << endl;
    return 0;
}
// TAG: LIS 最长不升 Dilworth 二分 O(nlogn)

P1091[NOIP2004 提高组] 合唱队形NOIP2004 提高普及/提高-

题意

n

名同学各有身高，要求出列若干人后剩下的队形先升后降（存在一个峰顶）。求最少出列多少人。

为什么选它

典型的双向 LIS：正着做一遍「以

i

结尾的最长上升」

up[i]

，反着做一遍「从

i

起的最长下降」

down[i]

，再枚举峰顶

i

——它教会你 LIS 不止正向一种跑法，正反两遍再拼接是一大类题的通法。

转移 · 复杂度

峰顶在

i

的合唱队形长

up[i]+down[i]-1

，答案

n-\max_i(up[i]+down[i]-1)

；时间

O(n^2)

（

n\le 100

足够）。

参考代码（双向 LIS + 枚举峰顶）

C++

在洛谷打开 P1091

#include <algorithm>
#include <iostream>
using namespace std;

int n, ans, a[105];
int up[105], down[105];          // up[i]：以 i 结尾的最长上升；down[i]：从 i 起的最长下降

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++)         // 正向：每人左侧的最长上升
    {
        up[i] = 1;
        for (int j = 1; j < i; j++)
        {
            if (a[j] < a[i])
            {
                up[i] = max(up[i], up[j] + 1);
            }
        }
    }

    for (int i = n; i >= 1; i--)         // 反向：每人右侧的最长下降
    {
        down[i] = 1;
        for (int j = n; j > i; j--)
        {
            if (a[j] < a[i])
            {
                down[i] = max(down[i], down[j] + 1);
            }
        }
    }

    for (int i = 1; i <= n; i++)         // 枚举峰顶 i，合唱队形长 up[i]+down[i]-1
    {
        ans = max(ans, up[i] + down[i] - 1);
    }

    cout << n - ans << endl;             // 最少出列 = 总人数 − 最长合唱队形
    return 0;
}
// TAG: 线性DP 双向LIS 枚举峰顶

练习

P2782友好城市二维偏序转 LIS：把每座城市看成 (南岸坐标, 北岸坐标)，按南岸排序后，答案就是北岸坐标的最长上升子序列——排序消去一维，剩一维做 LIS。在洛谷打开

P1439【模板】最长公共子序列两个排列的 LCS：把 a 中每个值映射成它在 a 里的位置，再把 b 按这个映射改写，b 的 LIS 长度就是答案，用 O(n log n) 二分。（亦属 A4 LCS。）在洛谷打开

P1725琪露诺LIS 思想的延伸——带区间转移的线性 DP：dp[i] 从 [i−r, i−l] 这段窗口取最大值转移，用单调队列把每步的区间最大值优化到 O(1)。在洛谷打开

最长上升子序列 LIS

本课摘要

什么是「上升子序列」

状态与转移：以某个数「结尾」

本质

跟着算一遍

看它一格一格长出来

深化：O(n log n) 贪心 + 二分

常见陷阱 · 严格上升 vs 不降

例题

练习