Pagini recente » Cod sursa (job #621619) | Cod sursa (job #2339862) | Cod sursa (job #1641611) | Cod sursa (job #419707) | Cod sursa (job #2692385)
// Mihai Priboi
#include <bits/stdc++.h>
#define MAXN 100000
int v[MAXN], best[MAXN], prev[MAXN], r[MAXN];
int main() {
FILE *fin, *fout;
int n, i, j, max;
fin = fopen( "scmax.in", "r" );
fscanf( fin, "%d", &n );
for( i = 0; i < n; i++ )
fscanf( fin, "%d", &v[i] );
fclose( fin );
// dinamica
best[0] = 1;
prev[0] = -1;
for( i = 1; i < n; i++ ) {
max = 0;
for( j = 0; j < i; j++ )
if( v[i] > v[j] && best[j] >= best[max] )
max = j;
if( max == 0 && v[i] <= v[max] ) {
best[i] = 1;
prev[i] = -1;
}
else {
best[i] = best[max] + 1;
prev[i] = max;
}
}
// maximul
max = 0;
for( i = 0; i < n; i++ )
if( best[i] > best[max] )
max = i;
// determinarea sirului
n = 0;
j = max;
while( j != -1 ) {
r[n++] = v[j];
j = prev[j];
}
fout = fopen( "scmax.out", "w" );
fprintf( fout, "%d\n", best[max] );
for( i = n - 1; i >= 0; i-- )
fprintf( fout, "%d ", r[i] );
fclose( fout );
return 0;
}