AcWing 895. 最长上升子序列 + 正序打印
原题链接
简单
作者:
轻微做题
,
2021-02-06 22:10:59
,
所有人可见
,
阅读 283
正序打印LIS
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
const int N = 1100;
vector<int> q;
stack<int> st;
int f[N], a[N], g[N];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++){
f[i] = 1;
for(int j = 1; j < i; j ++){
if(a[j] < a[i])
if(f[i] < f[j] + 1){
f[i] = f[j] + 1;
g[i] = j;
}
}
}
int k = 1;
for(int i = 1; i <= n; i ++) if(f[k] < f[i]) k = i;
cout << f[k] << endl;
int len = f[k];
for(int i = 1; i <= len; i ++){
st.push(a[k]);
k = g[k];
}
for(int i = 1; i <= len; i ++){
cout << st.top() << " ";
st.pop();
}
return 0;
}