Cod sursa(job #522415)

Utilizator ionut_ungureanuUngureanu Vladut Ionut ionut_ungureanu Data 15 ianuarie 2011 09:27:47
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include<stdio.h>
long long int n,a[100001],max,im,lg[100001],u[100001],i,j;
int main()
{
freopen("scmax.in","r",stdin);
freopen("scmax.out","w",stdout);

scanf("%d",&n);
for(i=1;i<=n;i++)
	scanf("%lld",&a[i]);

lg[n]=1;
u[n]=0;
for(i=n-1;i>=1;i--)
	{
	 max=0;
	 im=0;
	 for(j=i+1;j<=n;j++)
		 if(a[i]<a[j]&&max<lg[j])
			 max=lg[j],im=j;
	 lg[i]=max+1;
	 u[i]=im;
	}

max=lg[1];im=1;
for(i=2;i<=n;i++)
	if(max<lg[i])max=lg[i],im=i;

printf("%lld\n",max);
do
	{
	 printf("%lld ",a[im]);
	 im=u[im];
	}
while(im!=0);

return 0;
}