Cod sursa(job #824063)
#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;
}
void afisare( FILE* f, int* V, int k, int* pred ){
if( pred[k] > 0 ) afisare(f, V, pred[k], pred );
fprintf(f,"%d ",V[k] );
}
int main( int argc, char* argv[] ){
FILE* in = NULL;
FILE* out = NULL;
//deschidere fisire
in = fopen("scmax.in","r");
out = fopen("scmax.out","w");
int N; if(fscanf(in,"%d",&N));
int nr = 1; // initial length
int p = 0, i = 0, idx = 0, max = 0;
//Alocare de memorie
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) );;
v[0] = 0; // dummy value = 0
for( i = 1; i <= N; i++ )
if( fscanf(in,"%d",&v[i]) );
fclose(in);//inchidere fisier de intrare
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);
//Afisare sir
afisare(out, v, p, prev );
//inchidere fisire iesire
fclose(out);
//eliberare memorie
free(v);
free(M);
free(best);
free(prev);
return 0;
}