Pagini recente » Cod sursa (job #526322) | Cod sursa (job #729393) | Cod sursa (job #339535) | Cod sursa (job #448858) | Cod sursa (job #645685)
Cod sursa(job #645685)
#include<cstdio>
#include<cstring>
using namespace std;
void printArray( int a[], int n ){
for( int i=0; i<n; ++i ){
fprintf( stderr, "%d ", a[i] );
}
fprintf( stderr, "\n" );
}
void lcs( int a[], int n ){
int i,j,DP[n],P[n];
for( i=0; i<n; ++i ){
DP[i] = 1;
P[i] = -1;
}
int max,p;
for( i=1; i<n; ++i ){
max = -2000000000;
p = -1;
for( j=i-1; j>=0; --j ){
if( a[j] < a[i] && max < a[j] ){
max = a[j];
p = j;
}
}
if( p > -1 ){
DP[i] = DP[p]+1;
P[i] = p;
}
}
max = DP[0];
p = 0;
for( i=1; i<n; ++i ){
if( max < DP[i] ){
max = DP[i];
p = i;
}
}
int R[max];
for( i=max-1; i>=0; --i ){
R[i] = a[p];
p = P[p];
}
printf("%d\n", max);
for( i=0; i<max; ++i ){
printf("%d ", R[i]);
}
}
int main(){
freopen( "scmax.in", "r", stdin );
freopen( "scmax.out", "w", stdout );
int n,i;
scanf( "%d", &n );
int a[n];
for( i=0; i<n; ++i ){
scanf( "%d", &a[i] );
}
lcs( a, n );
}