Cod sursa(job #824035)
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int bineary_search( int *v, int *M, int left, int right, int x ){
int aux = right;
int mid = ( left + right ) / 2;
while ( left <= right ){
if( ( v[M[mid]] < x ) && ( x <= v[M[mid+1]] ) ) return mid;
else if( x > v[M[mid+1]] ){
left = mid + 1;
mid = ( left + right ) / 2;
}
else{
right = mid - 1;
mid = ( left + right ) / 2 ;
}
}
return aux;
}
int main( int argc, char* argv[] ){
FILE* in;
FILE* out;
in = fopen("scmax.in","r");
out = fopen("scmax.out","w");
int N; if(fscanf(in,"%d",&N));
int nr = 1; // initial length
int max = 0;
int p = 0, i = 0, idx = 0;
int* v = (int*)malloc( sizeof(int)*(N+1) );
int* M = (int*)malloc( sizeof(int)*(N+1) );
int* best = (int*)malloc( sizeof(int)*(N+1) );
int* prev = (int*)malloc( sizeof(int)*(N+1) );;
int* stack = (int*)malloc( sizeof(int)*(N+1) );
v[0] = 0; // dummy value = 0
for( i = 1; i <= N; i++ )
if( fscanf(in,"%d",&v[i]) );
fclose(in);
M[0] = 0; // dummy value = 0
M[1] = 1; // for v[1]
memset( best, 1, (N+1)*sizeof(int) );
memset( prev, -1, (N+1)*sizeof(int) );
for( i = 2; i <= N; i++ ){
idx = bineary_search( v, M, 0, nr, v[i] );
M[idx+1] = i;
prev[i] = M[idx]; // introduc in prev[i] cel mai mare element mai mic decat noul el introdus v[i]
best[i] = idx + 1;
if( best[i] > max ){
max = best[i];
p = i;
}
if( nr < idx + 1 )
nr++;
}
fprintf(out,"%d\n",max);
int k = 0;
while ( p > 0 ){
stack[k++] = v[p];
p = prev[p];
}
for( i = k-1 ; i >= 0 ; i-- )
fprintf(out,"%d ", stack[i] );
fclose(out);
free(v);
free(M);
free(best);
free(prev);
free(stack);
return 0;
}