最长上升子序列方案

📘 题意¶

给出一个由 $n(n \le 2 \cdot 10^5)$ 个不超过 $10^9$ 的正整数组成的序列。请输出该序列的：

最长上升子序列的长度
构造出一组合法的 LIS

🧪 60 分做法（朴素版）¶

该方法使用 $O(n^2)$ 的 DP 构造路径，仅适用于数据规模较小的情况。

💡 解题思路

令 f[i] 表示以第 i 个元素结尾的 LIS 长度
定义 g[i] 表示第 i 个位置是从哪个下标转移来的（路径记录）
- 每次转移中，如果 f[j] + 1 > f[i] 且 a[j] < a[i]，就更新：
- f[i] = f[j] + 1
- g[i] = j

答案构造

找到最长长度 ans，记录任意一个 f[i] == ans 的位置 i
从该位置不断回溯 i = g[i]，直到跳到起点为止
最后将路径 反向输出 即可

⏱️复杂度分析

时间复杂度：$O(n^2)$
空间复杂度：$O(n)$

示范代码

for (int i = 1; i <= n; i++) 
{
    f[i] = 1;
    for (int j = 1; j < i; j++) 
    {
        if (a[i] > a[j]) 
        {
            if (f[j] + 1 > f[i])
            {
                g[i] = j; // i 的上一个结尾是 j
                f[i] = f[j] + 1;
            }
        }
    }
    ans = max(ans, f[i]);
}
cout << ans << "\n";
int id = 0; // 找到一个结尾开始逆推
for (int i = 1; i <= n; i++)
{
    if (f[i] == ans)
    {
        id = i; // 随便哪个都行
    }
}
vector<int> ans;
for (int i = id; i >= 1; i = g[i]) // 类似于链表向前跳上一个结尾
{
    ans.push_back(a[i]);
}
reverse(ans.begin(), ans.end());
for (auto x : ans) cout << x << " ";

🥇 100 分做法（二分优化版）¶

在 $O(n \log n)$ 的 LIS 解法中，增加路径追踪即可实现构造。

💡 核心思路

利用辅助数组 d[] 来维护不同长度的上升子序列结尾，同时记录路径来源，实现 LIS 的同时构造路径。

准备工作

定义 pair<int, int> d[N]：
- d[i].first：长度为 i 的 LIS 的最小结尾值
- d[i].second：这个值对应的原数组下标（用于路径回溯）
定义：
- g[i]：记录当前位置的转移来源（来自哪个下标）
- f[i]：以 i 为结尾的 LIS 长度
- len：当前 LIS 的最大长度

流程实现

遍历每个元素 a[i]，对 LIS 状态和路径进行更新：

若 a[i] > d[len].first：
👉 可以作为长度为 len + 1 的 LIS 结尾
- g[i] = d[len].second（记录转移路径）
- d[++len] = {a[i], i}
- f[i] = len
否则（二分查找更新位置）：
👉 找到最早一个 d[pos].first >= a[i] 的位置
int pos = lower_bound(d + 1, d + len + 1, pair<int, int>(a[i], 0)) - d;
- g[i] = d[pos - 1].second（上一个长度为 $pos - 1$ 的结尾）
- d[pos] = {a[i], i}（更新该位置的结尾值）
- f[i] = pos

答案构造

在所有位置中找到 f[i] == len 的任意下标 $i$
从 $i$ 开始，根据 g[i] 逐步回溯
收集路径并倒序输出

⏱️ 复杂度分析

时间复杂度：$O(n \log n)$（LIS + 二分）
空间复杂度：$O(n)$（路径记录 + 状态）

代码

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e5 + 5;
int n, a[N], len, g[N], f[N];
pair<int, int> d[N];
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        if (a[i] > d[len].first)
        {
            g[i] = d[len].second; // 长为 len 的 LIS 结尾在下标 i
            d[++len] = {a[i], i};
            f[i] = len;
        }
        else
        {
            int pos = lower_bound(d + 1, d + len + 1, pair<int, int>(a[i], 0)) - d;
            g[i] = d[pos - 1].second;
            d[pos] = {a[i], i};
            f[i] = pos;
        }
    }
    cout << len << "\n";
    vector<int> ans;
    int id = 0;
    for (int i = 1; i <= n; i++)
    {
        if (f[i] == len)
        {
            id = i;
        }
    }
    for (int i = id; i >= 1; i = g[i])
    {
        ans.push_back(a[i]);
    }
    reverse(ans.begin(), ans.end());
    for (auto x : ans) cout << x << " "; 
    return 0;
}