Cod sursa(job #809064)

Utilizator cristina_hoameaCristina cristina_hoamea Data 7 noiembrie 2012 20:32:23
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>

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

int n, a[100001], lgmax[100001], maxim, urm[100001];
int poz;

void citire();
void pd();
void afisare();

int main()
{
    citire();
    pd();
    afisare();
    return 0;
}

void citire()
{
    int i;
    fin >>n;
    for(i=0; i<n; i++)
        fin>>a[i];
}

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

void afisare()
{
    int i;
    /*for(i=0; i<n-1; i++)
        if(lgmax[i]>lgmax[i+1])
            maxim=lgmax[i];
        else
            maxim=lgmax[i+1];*/
    fout<<maxim<<'\n';
	
	i=poz;
	while(i!=-1)
	{
		fout <<a[i]<<' ';
		i=urm[i];
	}
	fout <<'\n';
    fout.close();
}