Mai intai trebuie sa te autentifici.
Cod sursa(job #753358)
| Utilizator | Data | 29 mai 2012 21:02:59 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.99 kb |
#include <cstdio>
int a [100005], p [100005], best [100005], pre [100005], sol [100005];
void makesol (int pozmaxx) {
for (; pozmaxx; pozmaxx = pre [pozmaxx])
sol [++ sol [0]] = pozmaxx;
}
void writesol () {
int i;
for (i = sol [0]; i >= 1; -- i)
printf ("%d ", a [sol [i]]);
printf ("\n");
}
int main () {
freopen ("intervale2.in", "r", stdin);
freopen ("intervale2.out", "w", stdout);
int n, i, j, pozmaxx, maxx;
scanf ("%d", &n);
for (i = 1; i <= n; ++ i)
scanf ("%d", &a [i]);
for (i = 1; i <= n; ++ i)
scanf ("%d", &p [i]);
for (i = 1; i <= n; ++ i) {
maxx = 0;
pozmaxx = 0;
for (j = i - 1; j >= 1; -- j) {
if (best [j] > maxx && a [j] < a [i]) {
maxx = best [j];
pozmaxx = j;
}
}
best [i] = maxx + 1;
pre [i] = pozmaxx;
}
maxx = -1;
for (i = 1; i <= n; ++ i)
if (best [i] > maxx) {
pozmaxx = i;
maxx = best [i];
}
printf ("%d\n", maxx);
makesol (pozmaxx);
writesol ();
}
