深入解析最长上升子序列算法及其优化策略

核心逻辑与数学原理

最长上升子序列（Longest Increasing Subsequence, LIS）是单序列线性动态规划的重要基础。给定一个长度为 $N$ 的序列 $A$，需要从中选出一个子序列 $A_{p_1}, A_{p_2}, ext{...}, A_{p_k}$，使得下标满足 $p_1 < p_2 < ext{...} < p_k$ 且数值严格单调递增，即 $A_{p_1} < A_{p_2} < ext{...} < A_{p_k}$，求 $k$ 的最大值。

$O(N^2)$ 的朴素状态空间：每个位置 $i$ 的最优解仅依赖于在其之前且数值比它小的位置 $j$。通过枚举前驱进行状态转移，由于每个状态需要扫描 $O(N)$ 个前驱，总复杂度为 $O(N^2)$。
$O(N \log N)$ 的二分优化（贪心降维）：朴素算法的瓶颈在于：为了找到最大值，遍历了大量冗余的前驱状态。引入贪心策略：若两个上升子序列长度相同，末尾元素越小的那个，后续承接新元素的能力越强（潜力更大）。因此，定义一个辅助数组 $D$，其中 $D[len]$ 表示当前所有长度为 $len$ 的上升子序列中，末尾元素的最小值。
数学单调性证明：辅助数组 $D$ 具有严格的单调递增性，即 $D[1] < D[2] < ext{...} < D[len]$。 证明简述：若存在 $D[i] \ge D[i+1]$，根据定义，长度为 $i+1$ 的子序列倒数第二项必严格小于最后一项 $D[i+1]$，则可截取其前 $i$ 项构成一个末尾元素更小的长度为 $i$ 的子序列，其末尾元素必定小于 $D[i+1] \le D[i]$，这与 $D[i]$ 是长度为 $i$ 的子序列末尾最小值的定义矛盾。利用 $D$ 数组的严格单调性，对于每个新加入的元素 $A[i]$，无需遍历前驱，可直接通过二分查找（Binary Search）在 $O(\log N)$ 时间内定位并更新 $D$ 数组，将全局复杂度降至 $O(N \log N)$。

状态设计与算法推导

1. $O(N^2)$ 朴素算法

状态设计：$f[i]$ 表示以 $A[i]$ 结尾的最长上升子序列的长度。
转移方程：

$$f[i] = \max_{1 \le j < i, A[j] < A[i]} \{ f[j] \} + 1$$

边界条件为 $f[i] = 1$（自身独立成链）。

2. $O(N \log N)$ 贪心变维

状态设计：不维护以谁结尾，改为维护全局特征。$D[len]$ 表示长度为 $len$ 的上升子序列的最小结尾数值。同时用变量 $g ext{\_len}$ 记录当前已知的最长上升子序列的最大长度。
转移与更新逻辑：顺序扫描序列中的每一个元素 $A[i]$：
情况 A：若 $A[i] > D[g ext{\_len}]$，说明 $A[i]$ 可以直接接在当前最长子序列的后面，构成更长的子序列。令 $g ext{\_len} = g ext{\_len} + 1$，并拓展 $D[g ext{\_len}] = A[i]$。
情况 B：若 $A[i] \le D[g ext{\_len}]$，说明 $A[i]$ 无法拓展最大长度，但它可以优化某个既有长度的子序列结尾。在单调递增数组 $D[1 \dots g ext{\_len}]$ 中，利用二分查找（C++ 中为 lower_bound）定位到第一个大于或等于 $A[i]$ 的位置 $D[p]$，将其替换为更小、更有潜力的 $A[i]$。即：$D[p] = A[i]$。
最终答案：全局最长上升子序列长度即为 $g ext{\_len}$。

C++ 标准源码（NOIP风格）

以下源码在一个程序中展示了 $O(N^2)$ 与 $O(N \log N)$ 两种算法的实现，重点演示二分优化的工程规范，通过 Linux g++ -O2 编译验证。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
int a[MAXN];
int f[MAXN]; // 用于 O(N^2) 的状态数组
int d[MAXN]; // 用于 O(N log N) 的贪心增量数组

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

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

    // ==================== 1. O(N^2) 朴素算法 ====================
    int ans_n2 = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = 1;
        for (int j = 1; j < i; ++j) {
            if (a[j] < a[i]) { // 严格上升条件
                f[i] = max(f[i], f[j] + 1);
            }
        }
        ans_n2 = max(ans_n2, f[i]);
    }

    // ==================== 2. O(N log N) 二分优化 ====================
    int g_len = 0;
    // 致命踩坑点：d 数组存储的是数值，不是下标，且必须保持严格单调性
    for (int i = 1; i <= n; ++i) {
        if (g_len == 0 || a[i] > d[g_len]) {
            // 情况 A：比当前所有能构成的最长上升子序列的末尾还要大，直接接在后面
            g_len++;
            d[g_len] = a[i];
        } else {
            // 情况 B：二分查找到第一个大于等于 a[i] 的元素位置并替换它
            // d + 1 到 d + g_len + 1 是有效的一维检索区间
            int p = lower_bound(d + 1, d + g_len + 1, a[i]) - d;
            d[p] = a[i]; // 贪心修正：用更小的末尾元素替换旧的较大元素
        }
    }

    cout << "O(N^2) Ans: " << ans_n2 << "\n";
    cout << "O(N log N) Ans: " << g_len << "\n";

    return 0;
}

NOIP 实战避坑指南

1. 严格上升与非严格上升的二分函数混淆

现象：题目要求最长严格上升子序列（$A[i] > A[j]$），选手在二分优化时误用了 upper_bound。或者题目要求非降上升子序列（$A[i] \ge A[j]$），误用了 lower_bound。这会导致相同数值的元素处理逻辑错误，直接爆发逻辑零分。
规避手段：
求严格上升（不能有重复值）：使用 lower_bound（查找第一个 $\ge A[i]$ 的位置并替换，从而阻止相同元素并存）。
求非严格上升（可以有重复值）：使用 upper_bound（查找第一个 $> A[i]$ 的位置并替换，允许相同元素排在后面）。

2. 误以为 $D$ 数组存储的是最终的最长上升子序列

现象：部分选手在输出方案时，直接将更新到最后的 $D$ 数组当做 LIS 本身进行打印。这是严重的几何概念错误。$D$ 数组仅代表各个长度下对应的“潜力末尾值”，在更新过程中，其内部元素的相对先后顺序可能早已经脱离了原序列的索引拓扑结构。
规避手段：若题目要求输出具体方案，必须引入一个前驱指针数组 pre[i]，在 $O(N \log N)$ 维护过程中记录每个元素实际接在哪个元素的后面，最后从末尾倒序追溯。

经典 NOIP/洛谷真题

1. 洛谷 P1020 [NOIP1999 普及组] 导弹拦截

题意描述：某国为了防御敌方的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发导弹能够到达任意的高度，但是以后每一发导弹都不能高于前一发的高度。输入一组导弹依次飞来的高度，求：1. 这套系统最多能拦截多少枚导弹；2. 要拦截所有导弹最少要配备多少套这种导弹拦截系统。
问题本质与解题思路：
第一问本质：求最长不上升子序列。直接使用 $O(N \log N)$ 算法，由于是非严格下降，将序列反转或在二分时自定义比较算子（或者通过 upper_bound 配合相反单调性）进行贪心维护。
第二问本质：根据 Dilworth 定理（偏序集的最少反链划分数等于其最长链的长度），将一个序列划分为最少数量的不上升子序列，其系统套数恰好等于该序列的最长上升子序列（严格上升）的长度。直接套用上一节的 lower_bound 优化模板即可秒杀。

2. 洛谷 P1439 【模板】最长公共子序列

题意描述：给出两个长度为 $N$ 的排列 $P_1$ 和 $P_2$，求它们的最长公共子序列（LCS）长度。$N \le 100000$。
问题本质与解题思路：由于 $N$ 的范围达到了 $10^5$，传统的 $O(N^2)$ 朴素 LCS 算法必然 TLE。由于题目给出的两个序列均是 $1 \dots N$ 的全排列，每个数字在两个序列中均唯一出现，这意味着可以将 LCS 问题转化为 LIS 问题。
核心思路：以第一个排列 $P_1$ 为基准，将其中的数字重新映射为索引坐标 $1, 2, \dots, N$。然后将第二个排列 $P_2$ 中的每个数字根据刚才建立的映射关系替换为对应的坐标。因为 $P_1$ 在新坐标系下是严格单调递增的，所以 $P_2$ 的新序列与 $P_1$ 的公共子序列，在新坐标系下也必须是严格单调递增的。对替换后的 $P_2$ 新序列求最长上升子序列（LIS），即可在 $O(N \log N)$ 时间内解决原本 $O(N^2)$ 的 LCS 问题。