Cod sursa(job #501842)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 16 noiembrie 2010 20:02:32
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>

const int maxn=100001;
int i,N,max,pmax,a[maxn],Smax[maxn],pre[maxn],next[maxn];

void citire()
{
	scanf("%d",&N);
	for(i=1;i<=N;i++) scanf("%d",&a[i]);
}

void pd()
{
	int j;
	Smax[0]=0; pre[0]=-1; max=-1;
	for(i=1;i<=N;i++)
	{
		for(j=0;j<i;j++)
		{
			if(a[j]<a[i] && Smax[j]+1>Smax[i])
			{
				Smax[i]=Smax[j]+1;
				pre[i]=j;
				if(Smax[i]>max)
				{
					max=Smax[i]; pmax=i;
				}
			}
		}
	}
}

void constr()
{
	int nr;
	next[0]=nr=max;
	for(i=pmax;pre[i]!=-1;i=pre[i])
	{
		next[nr--]=i;
	}
}

int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	citire();
	pd();
	constr();
	printf("%d\n",max);
	for(i=1;i<=next[0];i++) printf("%d ",a[next[i]]);
}