Cod sursa(job #271954)

Utilizator AthanaricCirith Gorgor Athanaric Data 6 martie 2009 10:13:01
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <stdio.h>
#define N 101000
int v[N],lung[N],n,p[N],max,sol[N],k;
void Remake()
{
	int q=max;
	sol[++k]=v[q];
	while (q>=1)
	{
		int j=q-1;
		while (j && (lung[j]!=lung[q]-1 || v[j]>=v[q]))
			j--;
		if(j)
			sol[++k]=v[j];
		q=j;
	}
	for (int i=k; i>=1; i--)
		printf("%d ",sol[i]);
}
void Solve()
{
	scanf("%d",&n);
	for (int i=1; i<=n; i++)
		scanf("%d",&v[i]);
	lung[1]=1;
	for (int i=2; i<=n; i++)
	{
		max=0;
		for (int j=1; j<i; j++)
			if (v[j]<v[i] && lung[j]>max)
				max=lung[j];
		lung[i]=1+max;
	}
	max=1;
	for (int i=1; i<=n; i++)
		if (lung[i]>lung[max])
			max=i;
	printf("%d\n",lung[max]);
	Remake();

}
int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	Solve();
}