Cod sursa(job #300188)

Utilizator Ionutz_LalaLala Marius Ionut Ionutz_Lala Data 7 aprilie 2009 11:54:31
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include<cstdio>
#include<vector>
using namespace std;
int n,v[100005],best[100005],t[100005],maxim,poz;
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;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],poz=i;
	}
	printf("%d\n",maxim+1);
	do
	{
		afis.push_back(v[poz]);
		poz=t[poz];
	}while(poz);
	for(i=afis.size()-1;i>=0;i--) printf("%d ",afis[i]);
	printf("\n");
}