Cod sursa(job #2623397)

Utilizator euyoTukanul euyo Data 3 iunie 2020 08:53:12
Problema Subsir crescator maximal Scor 70
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h>

int v[100001];
int L[100001];
int c[100001];

int main() {
  FILE *fin = fopen( "scmax.in", "r" );
  FILE *fout = fopen( "scmax.out", "w" );
  int n, i, j, max, in, antin;

  fscanf( fin, "%d", &n );
  for ( i = 1; i <= n; ++i ) {
    fscanf( fin, "%d", &v[i] );
  }
  for ( i = n; i >= 1; --i ) {
    max = 0;
    for ( j = i; j <= n; ++j ) {
      if ( v[j] > v[i] ) {
        if ( max < L[j] ) {
          c[i] = j;
          max = L[j];
        }
      }
    }
    L[i] = max + 1;
  }
  max = 0;
  for ( i = 1; i <= n; ++i ) {
    if ( max < L[i] ) {
      max = L[i];
      in = i;
    }
  }
  fprintf( fout, "%d\n", max );
  antin = in - 1;
  while ( antin < in ) {
    fprintf( fout, "%d ", v[in] );
    antin = in;
    in = c[in];
  }
  fclose( fin );
  fclose( fout );
  return 0;
}