Pagini recente » Monitorul de evaluare | Istoria paginii utilizator/rbtand19 | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #698775)
Cod sursa(job #698775)
#include <cstdio>
#include <iostream>
using namespace std;
struct dinamica {
int l;
int r;
};
dinamica d[100005];
int n, v[100005], maxim, sol[100005];
int main()
{
int i, j;
freopen ("scmax.in", "r", stdin);
freopen ("scmax.out", "w", stdout);
scanf("%d", &n);
d[0].l = 1;
d[0].r = 0;
d[1].l = 1;
d[1].r = 0;
scanf("%d", &v[1]);
for(i = 2; i <= n; ++i) {
scanf("%d", &v[i]);
maxim = 0;
for(j = 1; j < i; ++j) {
if(v[i] > v[j] && d[j].l >= d[maxim].l)
maxim = j;
}
d[i].l = d[maxim].l + 1;
d[i].r = maxim;
}
maxim = -1;
for(i = 1; i <= n; ++i)
if(d[i].l > d[maxim].l)
maxim = i;
printf("%d\n", d[maxim].l - 1);
sol[++sol[0]] = v[maxim];
while(d[maxim].r > 0) {
sol[++sol[0]] = v[d[maxim].r];
maxim = d[maxim].r;
}
for(i = sol[0]; i >= 1; --i)
printf("%d ", sol[i]);
return 0;
}