Cod sursa(job #336630)

Utilizator pykhNeagoe Alexandru pykh Data 31 iulie 2009 22:19:08
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<stdio.h>
#define N 100005
int v[N], best[N], maxim, n, i,max1=0;

int max(int poz)
	{int sol=0, j;
		for(j=poz+1;j<=n;j++)
				if(v[j]>v[poz] && best[j]>best[sol])sol=j;	
		return sol;
}

void dinamic()
	{int k;
		for(i=n;i>=1;--i)
		{
		k=max( i);
		if(!k)best[i]=1;
		else 	{
			best[i]=best[k]+1; 
			if(best[i]>max1)
				{
					max1=best[i];
					maxim=i;}}
			}
	}
	
void afisare()

	{int k=best[maxim];
		printf("%d\n",best[maxim]);
		for(i=1;i<=n && k;i++)
			if(best[i]==k){printf("%d ",v[i]);--k;}
	}
	
int main()
	{
		freopen("scmax.in","r",stdin);
		freopen("scmax.out","w",stdout);
		scanf("%d",&n);
		for(i=1;i<=n;i++)
			scanf("%d",&v[i]);
		dinamic();
		afisare();
		return 0;
}