1、背景

求数值严格单调递增的子序列的长度最长是多少。（求最长上升子序列的最大长度）

对应的两种不同的方法，分别是

• 1、$O(n^2)$复杂度， AcWing 895. 最长上升子序列
• 2、$O(nlogn)$复杂度， AcWing 896. 最长上升子序列 II

2、输出最长上升子序列的最小字典序问题

此题来自 最长递增子序列

题目描述

给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）

输入格式

第一行包含整数N。

第二行包含N个整数，表示完整序列。

数据范围

$1 <= N <= 10^5$
$1 <= 数列中的数 <= 10^9$

输入样例：

9
2 1 5 3 6 4 8 9 7

输出样例：

1 3 4 8 9

输入样例：

5
1 2 8 6 4

输出样例：

1 2 4

算法分析

• 1、先求出到每个位置最长上升子序列的值f[i]，并计算出数组最长上升子序列的长度len
• 2、初始化t = len，从后往前枚举，找到最偏后且满足f[i] == t的值，表示最长上升子序列长度是t的最后一个元素是a[i]，更新t = t - 1，继续往前找

证明：在计算 f[i] 的过程中，若存在 f[x] == f[y] (x < y)，会存在 3 种情况

• 1、当a[x] < a[y]时，则 f[y] 可以从 f[x] 转移过来，因此 f[y] > f[x]，与假设矛盾
• 2、当a[x] == a[y]时，则在长度是 t = f[x] 的最长上升子序列中，最后一个元素选 a[x] 和选 a[y] 均可
• 3、当a[x] > a[y]时，则在长度是 t = f[x] 的最长上升子序列中，一定选 a[y] 比选 a[x] 最优，例如{1, 5, 3}的序列，长度是 2 时 {1, 3} 比 {1, 5} 更优

时间复杂度$O(nlogn)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000000 +  10;

int n;
int a[N], q[N], f[N];
int temp[N];

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

    int len = 0;
    for(int i = 1;i <= n;i ++)
    {
        int l = 0, r = len;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        q[l + 1] = a[i];
        len = max(len, l + 1);
        f[i] = l + 1;
    }
    for(int i = n, t = len;i >= 1;i --)
    {
        if(f[i] == t)
        {
            temp[t] = a[i];
            t --;
        }
        if(t == 0) break;
    }
    for(int i = 1;i <= len;i ++)
    {
        cout << temp[i] << " ";
    }
    cout << endl;

    return 0;
}