如何求最长上升子序列具体方案?
作者:
诺亚方舟.
,
2021-09-03 21:42:51
,
所有人可见
,
阅读 366
OJ:牛客网:NC91 最长递增子序列
算法基础课题目链接
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N];
int q[N]; // 不同长度下上升子序列结尾的最小值
int f[N]; // 以a[i]结尾最长上升子序列长度
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
int len = 0;
for (int i = 0; i < n; i++)
{
int l = 0, r = len; // 最大长度(q的长度)
while (l < r)
{
int mid = l + r + 1 >> 1;
if (q[mid] < a[i]) l = mid; //找到最后一个<a[i]的位置
else r = mid - 1;
}
len = max(len, r + 1);
q[r + 1] = a[i];
f[i] = r + 1;
}
printf("%d\n", len);
vector<int> res(len);
for (int i = n - 1, j = len; j >= 1; i--) //从后往前推
if (f[i] == j)
res[ -- j] = a[i];
for (auto x: res)
cout << x << ' ';
return 0;
}