Cod sursa(job #613404)

Utilizator biroBiro Alexandru biro Data 24 septembrie 2011 10:33:33
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <algorithm>
#define DIM 100010

using namespace std ;

int a[DIM] , a1[DIM] , a2[DIM] ;

int main() {
  freopen ("scmax.in","r",stdin) ;
  freopen ("scmax.out","w",stdout) ;

  int n ;

  scanf ("%d" , &n) ;
  for (int i=1 ; i<=n ; ++i) {
    scanf ("%d" , &a[i]) ;
  }
  
  int maxim=0 ;
  int poz ;
  
  for (int i=n ; i>=1 ; --i) {
    maxim=0 ;
    poz=-1 ;
    for (int j=i ; j<=n ; ++j) {
      if (a[i]<a[j]) {
        if (maxim<a1[j]) {
          maxim=a1[j] ;
          poz=j ;
        }
      }
    }
    a1[i]=maxim+1 ;
    a2[i]=poz ;
  }
  maxim=-1 ;
  for (int i=1 ; i<=n ; ++i) {
    if (a1[i]>maxim)
      maxim=a1[i] ;
  }
  printf ("%d\n" , maxim) ;
  int x ;
  for (int i=1 ; i<=n ; ++i) {
    if (a1[i]==maxim) {
      x=i ;
      while (x!=-1) {
        printf ("%d " , a[x]) ;
        x=a2[x] ;
      }
      break ;
    }
  }

  return 0 ;
}