Cod sursa(job #628560)

Utilizator selea_teodoraSelea Teodora selea_teodora Data 1 noiembrie 2011 17:39:32
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream>
using namespace std;
int n, a[1005],d[1005],solutie[1005];
int main()
{
	ifstream fin("scmax.in");
	ofstream fout("scmax.out");
	fin>>n;
	int i;
int 	maxim=0, pozitie,nr=0;
	for(i=1;i<=n;i++)
		fin>>a[i];
	d[1]=1;
	for(i=2;i<=n;i++)
	{
	    d[i]=1;
		for(int j=1;j<i;j++)
			if(a[j]<a[i])
				if(d[i]<=d[j])
				{
					d[i]=d[j]+1;
					if(maxim<d[i])
					{
						maxim=d[i];
						pozitie=i;
					}
				}
	}
	fout<<maxim<<'\n';
	solutie[1]=pozitie;
	nr=1;
	for(i=pozitie-1;i>=1;--i)
	{
		if(d[solutie[nr]]-1==d[i]&&a[solutie[nr]]>a[i])
			solutie[++nr]=i;
	}
	for(i=nr;i>=1;i--)
		fout<<a[solutie[i]]<<" ";
	fout<<'\n';
	return 0;
}