Cod sursa(job #543023)

Utilizator BMCBou Marian Catalin BMC Data 27 februarie 2011 14:16:18
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
//Bou Marian Catalin
#include<stdio.h>

long n, v[100003], val[100003], p[100003];

void afis(long a)
{
  if(a==0) return;
  afis(p[a]);
  printf("%ld ",v[a]);
}

int main()
{
  long i,j, nr=0, max;
  freopen("scmax.in", "r", stdin);
  freopen("scmax.out", "w", stdout);
  scanf("%ld", &n);
  for(i=1;i<=n;i++)
    scanf("%ld",v+i);
  
  //val[1]=0;
  //p[1]=0;
  v[0]=0; val[0]=0;
  max=0;
  
  for(i=1;i<=n;i++)
  {
    for(j=i-1;j>0 && v[i]<=v[j];--j);
    p[i]=j;
    val[i]=val[j]+1;
    if(val[max]<val[i])max=i;
  }
  
  printf("%ld\n", val[max]);
  afis(max);
  printf("\n");
  
  return 0;
}