Cod sursa(job #674288)

Utilizator RadEmanuelRad Emanuel RadEmanuel Data 5 februarie 2012 23:05:00
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include<stdio.h>
using namespace std;
int i,j,n,t[100001],l[100001],poz[100001],max,p;
void din()
{
	for(i=n-2;i>=0;--i)
		for(j=i+1;j<n;++j)
			if(t[i]<t[j] && l[i]<l[j]+1)
			{
				l[i]=l[j]+1;
				poz[i]=j;
				if(max<l[i]) {max=l[i]; p=i;} 
			}
}
int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	for(i=0;i<n;++i)
		scanf("%d",&t[i]);
	for(i=0;i<n;++i) l[i]=1;
	din();
	printf("%d\n",max);
	i=p;
	do
	{
		printf("%d ",t[i]);
		i=poz[i];
	}while(!(l[i]==1));
	printf("%d\n",t[i]);
	return 0;
}