Pagini recente » Cod sursa (job #1719712) | Cod sursa (job #1391263) | Cod sursa (job #1391272) | Cod sursa (job #1411872) | Cod sursa (job #1719710)
#include<stdio.h>
#define NMAX 100000
int a[NMAX], best[NMAX], pos[NMAX];
int compute(int n, int *max) {
int i, j, p;
best[n] = 1;
pos[n] = -1;
*max = 1;
p = n;
for(i = n-1; i >= 0; i--) {
best[i] = 1;
pos[i] = -1;
for(j = i; j <= n; j++ ) {
if(a[i] < a[j] && best[i] < best[j] + 1) {
best[i] = best[j]+1;
pos[i] = j;
p = i;
if(*max < best[i]) *max = best[i];
}
}
}
return p;
}
void display(int p, int max) {
int i = p;
printf("%d\n", max);
while(pos[i] != -1) {
printf("%d ", a[pos[i]]);
i = pos[i];
}
printf("\n");
}
int main() {
freopen("scmax.in", "r", stdin);
freopen("scmax.out", "w", stdout);
int N, max, end_pos;
scanf("%d", &N);
for(int i = 0; i < N; i++) {
scanf("%d", &a[i]);
}
end_pos = compute(N, &max);
display(end_pos, max);
return 0;
}