Cod sursa(job #824063)

Utilizator lucky1992Ion Ion lucky1992 Data 25 noiembrie 2012 20:30:38
Problema Subsir crescator maximal Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.91 kb
#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;
}