Cod sursa(job #1841447)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 5 ianuarie 2017 17:22:09
Problema Subsir crescator maximal Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>

#define MAX_N 100003

int L[MAX_N], best[MAX_N], poz[MAX_N];

int main() {
  FILE *fin, *fout;
  int i, j, n, max, sol, p;

  fin = fopen( "scmax.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 1; i <= n; i++ )
    fscanf( fin, "%d", &L[i] );
  fclose( fin );

  best[n] = 1;
  poz[n] = -1;
  max = 1;
  p = n;
  for ( i = n - 1; i >= 1; i-- ) {
    best[i] = 1;
    poz[i] = -1;
    for ( j = i + 1; j <= n; j++ )
      if ( L[i] < L[j] && best[i] < best[j] + 1 ) {
        best[i] = best[j] + 1;
        poz[i] = j;
        if ( best[i] > max )
          max = best[i];
        p = i;
    }
  }
  fout = fopen( "scmax.out", "w" );
  fprintf( fout, "%d\n", max );
  i = p;
  while ( i != - 1 ) {
    fprintf( fout, "%d ", L[i] );
    i = poz[i];
  }
  fclose( fout );

  return 0;
}