Cod sursa(job #1857724)

Utilizator isa_edi_cristeaEdi Cristea isa_edi_cristea Data 26 ianuarie 2017 16:13:48
Problema Subsir crescator maximal Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 1.01 kb
#include <stdio.h>

#define NMAX 100000


int v [ NMAX ] ;
int l [ NMAX ] ;
int nr [ NMAX ] ;

int main() {

  FILE *fin, *fout ;
  fin = fopen ("scmax.in", "r" ) ;
  fout = fopen ("scmax.out", "w" ) ;

  int n, i, j, max, poz, count ;
  fscanf (fin, "%d", &n ) ;

  for (i = 0 ; i < n ; i++ ) {
    fscanf (fin, "%d", &v[i] ) ;
  }

  l[0] = 1 ;
  for (i = 1 ; i < n ; i++ ) {
    max = 0 ;
    for (j = i-1 ; j >= 0 ; j-- ) {
      if (l[j] > max && v[j] < v[i] ) {
        max = l[j] ;
      }
    }
    l[i] = max + 1 ;
  }

  max = 0 ;
  poz = 0 ;
  for (i = 0 ; i < n ; i++ ) {
    if (l[i] > max ) {
      max = l[i] ;
      poz = i ;
    }
  }

  fprintf (fout, "%d\n", max ) ;

  count = 0 ;
  nr[count] = v[poz] ;
  count++;
  for (j = poz ; j >= 0 ; j-- ) {
    if (v[j] < v[poz] && l[j] == l[poz]-1) {
      nr[count++] = v[j];
      poz = j ;
      j = poz;
    }
  }

  for (i = count-1; i >= 0 ; i-- ) {
    fprintf (fout, "%d ", nr[i] ) ;
  }
  return 0;
}