Cod sursa(job #300177)

Utilizator Anamaria20Cotirlea Anamaria Anamaria20 Data 7 aprilie 2009 11:53:03
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],pozitie,maxim;

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