Cod sursa(job #462738)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 13 iunie 2010 11:06:30
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <stdio.h>
long int lungime[100001],a[100001],indice[100001],n;

void date(){
long int i;
freopen ("scmax.in","r",stdin);
scanf("%ld\n",&n);
for(i=1;i<=n;i++)
scanf("%ld ",&a[i]);
}

int main(){
  long int i,j,max,pozmax;
  freopen("scmax.out","w",stdout);
  date();
  lungime[n]=1;
  indice[n]=0;
  max=1;
  pozmax=n;
  
  for(i=n-1;i>0;i--){
    lungime[i]=1;
    indice[i]=0;
    for(j=i+1;j<=n;j++){
    if((lungime[i]<=lungime[j])&&(a[i]<a[j])){
       lungime[i]=1+lungime[j];
       indice[i]=j;
       if(lungime[i]>max){
          max=lungime[i];
          pozmax=i;
       }
    }
    }               
    }
    
//determinare maxim
  //max=lungime[1];pozmax=1;
 //for(i=2;i<=n;i++)if(lungime[i]>max){max=lungime[i];pozmax=i;}
  //afisare solutie optima;
  printf("%ld\n",max);
  
  for(i=pozmax;i;i=indice[i]){
      printf("%ld ",a[i]); 
  }
  printf("\n");

return 0;
}