Cod sursa(job #809139)

Utilizator trifan_gabrielaTrifan Gabriela trifan_gabriela Data 7 noiembrie 2012 22:13:07
Problema Subsir crescator maximal Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n, x;
int a[1000], urm[1000], lgmax[1000];
int pozmax;

void afisare();
void pd();

int main()
{
	int i;
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>a[i];
	pd();
	afisare();
	return 0;
}

void pd()
{
	int i, j;
	lgmax[n]=1;
	urm[n]=-1;
    for(i=n-1; i>=1;i--)
	{
		lgmax[i]=1;
		urm[i]=-1;
        for(j=i+1; j<=n; j++)
            if(a[i]<=a[j] && lgmax[i]<lgmax[j]+1)
            {
                lgmax[i]=1+lgmax[j];
				urm[i]=j;
            }
	}
}

void afisare()
{
	int i;
	x=lgmax[1];
	pozmax=1;
	for(i=1;i<=n;i++)
		if(x<lgmax[i])
		{
			x=lgmax[i];
			pozmax=i;
		}
	fout<<x<<'\n';
	i=pozmax;
	while(i!=-1)
	{
		fout<<a[i]<<' ';
		i=urm[i];
	}
	fout <<'\n';
	fout.close();
}