Cod sursa(job #430030)

Utilizator soriynSorin Rita soriyn Data 30 martie 2010 18:11:48
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<stdio.h>


int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	int n;
	scanf("%d \n",&n);
	int v[n+1],l[n+1],max=-1,p,i,maxim,max2=0,cnt=1,sir[n+1],o=1;
	
	for(int i=1;i<=n;i++)
	{
		scanf("%d ",&v[i]);
	}
	l[n]=1;
	for(i=n-1;i>=1;i--)
	{   max=0;
		for(int j=i+1;j<=n;j++)
		   if (l[j]>max && v[i]<v[j])
		   {
			    max=l[j];
		
		   }
		l[i]=max+1;
			
	}

	for(int i=1;i<=n;i++)
		if(l[i]>=max2) {max2=l[i];p=i;}
if(max2==0) max2=1;
if(max2==1)
printf("1 \n%d",v[1]);
else{
maxim=v[p];
sir[1]=maxim;
for(int i=p;i<=n;i++)
 {  
	 if(l[i]==max2)
{
       if(v[i]>maxim) 
    {
	  o++;
	  sir[o]=v[i];
	  
	  maxim=v[i];
	  cnt++;
	}
	   max2--;
	   
 }

 
	
}
printf("%d\n",o);
for(int i=1;i<=o;i++)
printf("%d ",sir[i]);
}
	return 0;
}