Cod sursa(job #502363)

Utilizator drag0s93Mandu Dragos drag0s93 Data 19 noiembrie 2010 08:18:58
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 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]]);

}