Cod sursa(job #803298)

Utilizator Ionut228Ionut Calofir Ionut228 Data 27 octombrie 2012 12:44:01
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int n,i,j,m,p,maxim,im,pm,v[100],lun[100],pre[100],w[100];

void rezolvare ()
{
	lun[1]=1;
	pre[1]=-1;
	maxim=1;
	for(i=2;i<=n;i++)
	{
		m=0;
		p=-1;
		for(j=1;j<=i-1;j++)
		{
			if(v[j]<=v[i])
				if(lun[j]>m)
				{
					m=lun[j];
					p=j;
				}
		}
		lun[i]=1+m;
		pre[i]=p;
		if(lun[i]>=maxim)
		{
			im=i;
			maxim=lun[i];
			pm=pre[i];
		}
	}
}

int main ()
{
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	maxim=0;
	rezolvare();
	i=im;
	pm=pre[i];
	j=maxim;
	g<<maxim<<"\n";
	while(pre[i]!=-1)
	{
		w[j]=v[i];
		j--;
		i=pre[i];
	}
	w[j]=v[i];
	for(i=1;i<=maxim;i++)
		g<<w[i]<<" ";
	f.close();g.close();
	return 0;
}