最长上升子序列

#include <bits/stdc++.h>
using namespace std;

/*
测试用例：
8
-7 10  9  2  3  8  8  1
*/

const int N = 1e5 + 10;
int n, a[N];
int f[N], idx; // dp数组，idx:下标指针,因为从1开始，也可以理解为个数、LIS的最大长度
int pos[N];    // p数组，记录原始数组每个数字在dp数组中出现的位置,也就是这个数字a[i]它当过第几名

//输出一条LIS路径,判断需要配合Special Judge
void print() {
    vector<int> path;
    for (int i = n; i >= 1 && idx; i--) //找够idx个就结束了
        if (pos[i] == idx) {            //找到idx,idx-1,idx-2,...的名次
            path.push_back(a[i]);       //记录idx,idx-1,idx-2,...名次的数字入路径数组
            idx--;
        }
    for (int i = path.size() - 1; i >= 0; i--) printf("%d ", path[i]);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    // 1、出发
    f[++idx] = a[1];
    pos[1] = 1; //每个数字都会产生一个在f数组中的位置记录

    // 2、后续元素进行处理
    for (int i = 2; i <= n; i++)
        if (a[i] > f[idx]) {
            f[++idx] = a[i];
            pos[i] = idx; //每个数字都会产生一个在f数组中的位置记录
        } else {
            int t = lower_bound(f + 1, f + idx + 1, a[i]) - f;
            f[t] = a[i];
            pos[i] = t; //每个数字都会产生一个在f数组中的位置记录
        }
    //输出lis长度
    printf("%d\n", idx);

    //输出LIS路径方法
    print();

    return 0;
}