Pagini recente » Statistici Balici Andrei (andrei.balici) | Monitorul de evaluare | Rating Stoica Dan (danflorian10) | Statistici Lucacel Razvan (LucacelRazvan) | Cod sursa (job #596687)
Cod sursa(job #596687)
/*
* subsirCrescatorMaximal.c
*
* Created on: Jun 18, 2011
* Author: mihai
*/
#include <stdio.h>
#define MAX 100001
int i, j, N, nr[MAX], dim[MAX], indici[MAX], ultim = 0, max = 0;
void afiseaza_numere(int i) {
if (i == indici[i]) {
printf("%d ", nr[i]);
return;
}
afiseaza_numere(indici[i]);
printf("%d ", nr[i]);
}
int main() {
freopen("scmax.in", "r", stdin);
freopen("scmax.out", "w", stdout);
scanf("%d", &N);
for (i = 0; i < N; i++)
scanf("%d", &nr[i]);
dim[0] = 1;
indici[0] = 0;
for (i = 1; i < N; i++) {
if (nr[i] > nr[i - 1]) {
dim[i] = dim[i - 1] + 1;
indici[i] = i - 1;
if (dim[i] >= max) {
max = dim[i];
ultim = i;
}
} else if (nr[i] == nr[i - 1]) {
dim[i] = dim[i - 1];
indici[i] = indici[i - 1];
} else {
j = i - 1;
while (nr[i] < nr[j] && j != 0 && j != indici[j]) {
j = indici[j];
}
if (j == 0 || j == indici[j]) {
indici[i] = i;
dim[i] = dim[j];
} else {
indici[i] = j;
dim[i] = dim[j] + 1;
}
}
}
printf("%d\n", dim[ultim]);
afiseaza_numere(ultim);
return 0;
}