Cod sursa(job #502372)

Utilizator alexandra_naeNae Alexandra Beatrice alexandra_nae Data 19 noiembrie 2010 09:18:57
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<stdio.h>
int max,pmax,p,pred[100001],lung[100001],v[100001],n,i,j,pre[100001],nr;
void citire()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
}
void subsir(int p)
{
	if (pred[p]!=0)
		subsir(pred[p]);
	printf("%d ",v[p]);
}

	int main()
	{
		freopen("scmax.in","r",stdin);
		freopen("scmax.out","w",stdout);
		citire();
			lung[1]=1; pred[1]=0;
	for(i=2;i<=n;i++)
	{
		max=0;
		pmax=0;
		for(j=1;j<i;j++)
		{
			if (v[j]>=v[i]) continue;
			if(lung[j]>max)
			{
				max=lung[j];
				pmax=j;
			}
		}
			lung[i]=1+max;
			pred[i]=pmax;
	}
	
	max=-1;
	pmax=0;
		for(i=1;i<=n;i++)
		if(lung[i]>max)
		{
			max=lung[i];
            pmax=i;
        }
		
		printf("%d\n", max);
		subsir(pmax);
		return 0;
	}