Cod sursa(job #502371)

Utilizator alexandra_naeNae Alexandra Beatrice alexandra_nae Data 19 noiembrie 2010 09:16:23
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 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", pmax);
		subsir(pmax);
		return 0;
	}