Cod sursa(job #645685)

Utilizator tak3rStefan Mirea tak3r Data 10 decembrie 2011 12:23:22
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<cstdio>
#include<cstring>

using namespace std;

void printArray( int a[], int n ){
  for( int i=0; i<n; ++i ){
    fprintf( stderr, "%d ", a[i] );
  }
  fprintf( stderr, "\n" );
}

void lcs( int a[], int n ){
  int i,j,DP[n],P[n];
  
  for( i=0; i<n; ++i ){
    DP[i] = 1;
    P[i] = -1;
  }
  
  int max,p;
  
  for( i=1; i<n; ++i ){
    max = -2000000000;
    p   = -1;
    for( j=i-1; j>=0; --j ){
      if( a[j] < a[i] && max < a[j] ){
        max = a[j];
        p   = j;
      }
    }
    if( p > -1 ){
      DP[i] = DP[p]+1;
      P[i]  = p;
    }
  }
  
  max = DP[0];
  p = 0;
  for( i=1; i<n; ++i ){
    if( max < DP[i] ){
      max = DP[i];
      p = i;
    }
  }
  
  int R[max];
  for( i=max-1; i>=0; --i ){
    R[i] = a[p];
    p = P[p];
  }
  
  printf("%d\n", max);
  for( i=0; i<max; ++i ){
    printf("%d ", R[i]);
  }
  
}

int main(){

  freopen( "scmax.in", "r", stdin );
  freopen( "scmax.out", "w", stdout );
  
  int n,i;
  
  scanf( "%d", &n );
  
  int a[n];
  
  for( i=0; i<n; ++i ){
    scanf( "%d", &a[i] );
  }
  
  lcs( a, n );
  
}