Cod sursa(job #929864)

Utilizator avaspataruAva Spataru avaspataru Data 27 martie 2013 12:18:33
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<cstdio>
int n,i,j,max,maxl,lung[100001],v[100001],vc[100001],cn;
int main(){
  freopen("scmax.in","r",stdin);
  freopen("scmax.out","w",stdout);
  scanf("%d",&n);
  for(i=1;i<=n;i++)
      scanf("%d",&v[i]);
  for(i=1;i<=n;i++){
    max=0;
    for(j=1;j<i;j++)
        if(v[j]<v[i]&&lung[j]>max){
          max=lung[j];
        }
    lung[i]=max+1;
    if(maxl<lung[i]){
      maxl=lung[i];
      cn=v[i];
    }
  }
  printf("%d\n",maxl);
  int pp=1;
  int select=maxl-1;
  vc[maxl]=cn;
  for(i=n;i>=1&&pp==1;i--){
      if(lung[i]==select&&v[i]<cn){
        cn=v[i];
        vc[select]=v[i];
        select--;
      }
  }
  for(i=1;i<=maxl;i++)
    printf("%d ",vc[i]);
  return 0;
}