Cod sursa(job #393283)

Utilizator vicenzo_cnuStan Alexandru Dan vicenzo_cnu Data 9 februarie 2010 10:01:20
Problema Subsir crescator maximal Scor 20
Compilator c Status done
Runda Arhiva educationala Marime 0.6 kb
#include<stdio.h>
int main()
{freopen("scmax.in","r",stdin);
freopen("scmax.out","w",stdout);
int n=0,i=0,j=0,max=0,poz=0;
char log=0;
int v[100001];
int c[100001],d[100001];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&v[i]);
c[n-1]=-1;
d[n-1]=1;
  for(i=n-2;i>=0;i--)
    {log=0;
    for(j=i;j<n&&!log;j++)
      if(v[j]> v[i])
        {c[i]=j;
        d[i]=d[j]+1;
        log=1;}    
    if(log==0) 
    {d[i]=1;
    c[i]=-1;}

}
max=d[0];
poz=0;
for(i=1;i<=n-1;i++)
if(max<d[i])
{max=d[i];
poz=i;}
printf("%d\n",max);
while(poz!=-1)
{printf("%d ",v[poz]);
poz=c[poz];}
fclose(stdin);
fclose(stdout);
return 0;

}