Cod sursa(job #616848)

Utilizator selea_teodoraSelea Teodora selea_teodora Data 13 octombrie 2011 15:26:00
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<stdio.h>
using namespace std;
int s[100005],n,c[100005],imax,sol[100005];
void vector_caracteristic()
{
	c[1]=imax=1;
	int k,p;
	for(k=2;k<=n;k++)
		if(s[k]>s[imax])
		{
			c[k]=c[imax]+1;
			imax=k;
		}
		else
		{
			c[k]=1;
			p=k-1;
			while(p>0)
			{
				if(s[k]>s[p]&&(c[k]<=c[p]))
					c[k]=c[p]+1;
				p--;
			}
			if(c[k]==c[imax])
				imax=k;
		}
}
int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	int i,k;
	for(i=1;i<=n;i++)
		scanf("%d",&s[i]);
	vector_caracteristic();
	i=n;
	for(k=c[imax];k>0;k--)
		{
			while(c[i]!=k)
				i--;
			sol[k]=s[i];
		}
	printf("%d\n",c[imax]);
	for(i=1;i<=c[imax];i++)
		printf("%d ",sol[i]);
	printf("\n");
	return 0;
}