Cod sursa(job #433238)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 3 aprilie 2010 14:51:16
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<cstdio>
#define MAX_N 100005

using namespace std;


int N, v[MAX_N], D[MAX_N], k, i, j, poz, maxim, mx;

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]);
	D[N] = 1;
	
	for(k=N-1;k>=1;k--)
	{
		int mx=0;
		for(j=k+1;j<=N;j++)
			if(v[j]>v[k] && D[j]>mx)
				mx = D[j];
		D[k] = mx + 1;
		if(D[k] > maxim)
		{
			maxim = D[k];
			poz = k;
		}
	}
	
	printf("%d",maxim);
	printf("\n");
	printf("%d ",v[poz]);
	for(i=poz+1;i<=N;i++)
		if(D[i] == maxim - 1)
		{
			printf("%d ",v[i]);
			maxim--;
		}
	return 0;
}