Cod sursa(job #690749)

Utilizator D4n13LMuntean Dan Iulian D4n13L Data 25 februarie 2012 20:42:55
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<fstream>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int v[100001],x[100001],drum[100001];
int main()
{
	int i,j,k,l,nr=0,p,n,poz,max=-1,r;
	in>>n;
	for(i=1;i<=n;i++)
		in>>v[i];
	x[1]=1;
	for(i=2;i<=n;i++)
	{
		for(j=1;j<i;j++)
		{
			if(v[j]>=v[i])
				continue;
			if(x[j]>x[i])
				x[i]=x[j];
		}
		x[i]++;
		if(x[i]>max)
		{
			max=x[i];
			poz=i;
		}
	}
	out<<max<<"\n";
	j=1;
	drum[j]=v[poz];
	i=poz;
	for(r=poz-1;r>=1;r--)
	{
		if(v[r]>v[i])
			continue;
		if(x[i]-x[r]==1)
		{
			drum[++j]=v[r];
			i=r;
		}
	}
	for(i=j;i>=1;i--)
		out<<drum[i]<<" ";
}
//1 2 2 3 3 4 5 2