Cod sursa(job #336611)

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

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

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;
}