Pagini recente » Diferente pentru utilizator/ank_treize intre reviziile 2 si 1 | Cod sursa (job #1719709) | Cod sursa (job #1719711) | Diferente pentru utilizator/point intre reviziile 2 si 1 | Cod sursa (job #1719712)
#include<stdio.h>
#define NMAX 100001
int a[NMAX], best[NMAX], pos[NMAX];
int compute(int n, int *max) {
// p - position of the last element of the largest sequence
int i, j, p;
best[n] = 1;
pos[n] = -1;
*max = 1;
p = n;
for(i = n-1; i >= 1; 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;
if(*max < best[i]) {
*max = best[i];
p = i;
}
}
}
}
return p;
}
void display(int p, int max) {
int i = p;
printf("%d\n", max);
while(pos[i] != -1) {
printf("%d ", a[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 = 1; i <= N; i++) {
scanf("%d", &a[i]);
}
end_pos = compute(N, &max);
display(end_pos, max);
return 0;
}