Pagini recente » tema | Cod sursa (job #1162410) | Cod sursa (job #307308) | Cod sursa (job #641222) | Cod sursa (job #552311)
Cod sursa(job #552311)
/* Infoarena SCMAX (Subsir crescator maximal) http://infoarena.ro */
#include <stdio.h>
#define SIZE 110000
int n, a[SIZE];
int len[SIZE], t[SIZE];
void afis(int i)
{
if (i >= 0) {
afis(t[i]);
printf("%d ", a[i]);
}
}
int main(void)
{
int i, j, max, jmax;
freopen("scmax.in", "r", stdin);
freopen("scmax.out", "w", stdout);
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
len[0] = 1;
t[0] = -1;
for (i = 1; i < n; i++) {
max = 0;
jmax = -1;
for (j = 0; j < i; j++) {
if (a[j] < a[i] && max < len[j]) {
max = len[j];
jmax = j;
}
}
len[i] = max + 1;
t[i] = jmax;
}
max = len[0];
jmax = 0;
for (j = 1; j < n; j++) {
if (max < len[j]) {
max = len[j];
jmax = j;
}
}
printf("%d\n", max);
afis(jmax);
printf("\n");
return 0;
}