Cod sursa(job #300168)

Utilizator andrei92Andrei Socaciu andrei92 Data 7 aprilie 2009 11:51:00
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <cstdio>
#include <vector>
using namespace std;

int n, v[100005], best[100005], t[100005];
int maxim, pozitie;
vector <int> afis;

int main()
{
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);
	
	int i, j;
	scanf("%d", &n);
	for(i=1; i<=n; i++)
	{
		scanf("%d", &v[i]);
		for(j=i-1; j>=1; j--)
			if(v[i]>v[j] && best[i]<best[j]+1)
			{
				best[i] = best[j]+1;
				t[i]=j;
			}	
		if(best[i]>maxim) maxim	= best[i], pozitie = i;
	}	
	printf("%d\n", maxim+1);
	do
	{
		afis.push_back(v[pozitie]);
		pozitie = t[pozitie];
	}while(pozitie!=0);
	for(i=afis.size()-1; i>=0; i--)
		printf("%d ", afis[i]);
	printf("\n");
	return 0;	
}