Cod sursa(job #707855)

Utilizator BeniLehelBeni Lehel BeniLehel Data 6 martie 2012 08:00:03
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<stdio.h>
int t[100001]={0},b[100001]={0},ut[100000]={0},n,k=0;
int find(int i)
{
int ok=1;
for(int j=i-1;j>=0&&ok;j--)
if(t[i]>t[j] && b[i]-1==b[j])
{
ut[k]=t[j];
k++;
find(j);
ok=0;
}
return 0;
}
int main()
{
freopen("scmax.in","r",stdin);
freopen("scmax.out","w",stdout);
 
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&t[i]);
 
for(int i=0;i<n;i++)
{
int m=-1;
for(int j=i-1;j>=0;j--)
if(t[j]<t[i] && b[j]>m)
{
m=b[j];
b[i]=b[j]+1;
}
}
int m=0,mi;
for(int i=0;i<n;i++)
if(b[i]>m)
{
mi=i;
m=b[i];
}
ut[k]=t[mi];
k++;
find(mi);
 
/*for(int i=0;i<n;i++)
printf("%d ",t[i]);
printf("\n");
for(int i=0;i<n;i++)
printf("%d ",b[i]);
printf("\n");*/

printf("%d\n",k);
for(int i=k-1;i>=0;i--)
printf("%d ",ut[i]);
return 0;
}