Cod sursa(job #271946)

Utilizator zlatebogdanZlate Bogdan zlatebogdan Data 6 martie 2009 09:47:45
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<stdio.h>
#define N 100005
int a[N],n,lung[N],v[N];
void citire()
{
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;++i)
		scanf("%d",&a[i]);
}
void solve()
{
	int i,j,max,k=0;
	citire();
	lung[1]=1;
	for(i=2;i<=n;++i)
	{
		j=i-1;
		while(j&&a[i]<=a[j])
			--j;
		if(j==0)
			lung[i]=1;
		else
			lung[i]=lung[j]+1;
	}
	printf("%d\n",lung[n]);
	max=lung[n];
	i=n;
	while(lung[i]==lung[i-1])
		--i;
	v[++k]=a[i];
	while(i)
		if(lung[i]!=max-1)
			--i;
		else
		{
			v[++k]=a[i];
			max=lung[i];
			--i;
		}
	for(i=k;i>=1;--i)
		printf("%d ",v[i]);
}
int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	solve();
	return 0;
}