python/TangDou/AcWing/LIS/896_WithPrintPath.cpp

#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], fl;  // dp数组，fl:下标指针,因为从1开始，也可以理解为个数、LIS的最大长度
int pos[N];    // p数组，记录原始数组每个数字在dp数组中出现的位置,也就是这个数字a[i]它当过第几名

//输出一条LIS路径,判断需要配合Special Judge
void print() {
    vector<int> path;
    for (int i = n; i >= 1 && fl; i--) //找够fl个就结束了
        if (pos[i] == fl) {            //找到fl,fl-1,fl-2,...的名次
            path.push_back(a[i]);      //记录fl,fl-1,fl-2,...名次的数字入路径数组
            fl--;
        }
    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[++fl] = a[1];
    pos[1] = 1; //每个数字都会产生一个在f数组中的位置记录

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

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

    return 0;
}