Cod sursa(job #2692385)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 2 ianuarie 2021 16:05:22
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
// Mihai Priboi

#include <bits/stdc++.h>

#define MAXN 100000

int v[MAXN], best[MAXN], prev[MAXN], r[MAXN];

int main() {
  FILE *fin, *fout;
  int n, i, j, max;
  fin = fopen( "scmax.in", "r" );
  fscanf( fin, "%d", &n );

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

  fclose( fin );

  // dinamica
  best[0] = 1;
  prev[0] = -1;
  for( i = 1; i < n; i++ ) {

    max = 0;
    for( j = 0; j < i; j++ )
      if( v[i] > v[j] && best[j] >= best[max] )
        max = j;

    if( max == 0 && v[i] <= v[max] ) {
      best[i] = 1;
      prev[i] = -1;
    }
    else {
      best[i] = best[max] + 1;
      prev[i] = max;
    }
  }

  // maximul
  max = 0;
  for( i = 0; i < n; i++ )
    if( best[i] > best[max] )
      max = i;

  // determinarea sirului
  n = 0;
  j = max;
  while( j != -1 ) {
    r[n++] = v[j];
    j = prev[j];
  }

  fout = fopen( "scmax.out", "w" );

  fprintf( fout, "%d\n", best[max] );
  for( i = n - 1; i >= 0; i-- )
    fprintf( fout, "%d ", r[i] );

  fclose( fout );
  return 0;
}