Pagini recente » Cod sursa (job #1403524) | Cod sursa (job #3132661) | Cod sursa (job #2357537) | Cod sursa (job #1629156) | Cod sursa (job #698816)
Cod sursa(job #698816)
#include <cstdio>
#include <iostream>
using namespace std;
struct dinamica {
int l;
int r;
};
dinamica d[100005];
int n, v[100005], maxim, sol[100005], maxsol;
int main()
{
int i, j;
freopen ("scmax.in", "r", stdin);
freopen ("scmax.out", "w", stdout);
scanf("%d", &n);
d[0].l = 0;
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;
if(d[i].l > d[maxsol].l)
maxsol = i;
}
for(i = 1; i <= n; ++i)
cerr << d[i].l << ' ' << d[i].r << "\n";
printf("%d\n", d[maxsol].l);
sol[++sol[0]] = v[maxsol];
do {
sol[++sol[0]] = v[d[maxsol].r];
maxsol = d[maxsol].r;
}while(d[maxsol].r > 0);
for(i = sol[0]; i >= 1; --i)
printf("%d ", sol[i]);
return 0;
}