AcWing 895. 最长上升子序列+路径记录
原题链接
简单
作者:
CodeSlogan
,
2022-02-20 13:20:01
,
所有人可见
,
阅读 389
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N], f[N], pre[N];
int n;
void PrintPath(int v) {
if (pre[v] == 0) {
printf("%d", a[v]);
return;
}
PrintPath(pre[v]);
printf(" %d", a[v]);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ ) {
f[i] = 1; // 初始化,只有1个数以第i个数结尾
for (int j = 1; j < i; j++) {
if (a[j] < a[i]) {
if (f[i] < f[j] + 1) {
f[i] = f[j] + 1;
pre[i] = j;
}
}
}
}
int res = -1e9, t;
for (int i = 1; i <= n; i ++ ) {
if (f[i] > res) {
res = f[i];
t = i;
}
}
cout << res << endl;
PrintPath(t);
return 0;
}
太棒了!