Cod sursa(job #336600)

Utilizator pykhNeagoe Alexandru pykh Data 31 iulie 2009 21:04:16
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<stdio.h>
#define N 100005
int v[N], best[N], maxim, n, i;

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