Cod sursa(job #811275)

Utilizator teonasipoteanuTeona Sipoteanu teonasipoteanu Data 11 noiembrie 2012 20:09:57
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<fstream>

using namespace std;

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

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

int lgmax[1000010],a[1000010],urm[1000010],n;
int max1, max2; //pozitia maxima pe care se afla elem maxim

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

void citire()
{
    int i;
    fin>>n;
    for(i=1;i<=n;++i)
        fin>>a[i];
}
void pd()
{
    int i,j;
    lgmax[n]=max2=1;
    urm[n]=-1;
	max1=n;
	
    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])
				if(lgmax[i]<lgmax[j]+1 )
				{
					lgmax[i]=lgmax[j]+1;
					urm[i]=j;
					if(lgmax[i]>max2)
						{
							max2=lgmax[i];
							max1=i;
						}
				}
    }
}

void afisare()
{
    fout<<max2<<'\n';
    while(max1!=-1)
    {
        fout<<a[max1]<<' ';
        max1=urm[max1];
    }
}