Cod sursa(job #690185)

Utilizator GaborGabrielFMI - GabrielG GaborGabriel Data 25 februarie 2012 12:34:51
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");

long long n,i,maxim,j,mmaxim=0,pmax;
long long v[200005],prec[200005],s[200005],afis[200005];

int main()
{
    f>>n;
    for(i=1;i<=n;i++) f>>v[i];
    prec[1]=0;
    s[1]=1;
    i=2;
    while(i<=n)
    {
        maxim=0;
        for(j=i-1;j>=1;j--)
            if(v[i]>v[j] && (!maxim || s[maxim]<s[j]))
                maxim=j;
        if(!maxim) s[i]=1,prec[i]=0;
        else s[i]=s[maxim]+1,prec[i]=maxim;
        if(s[mmaxim]<s[i]) mmaxim = i;
        i++;
    }
    g<<s[mmaxim]<<'\n';
    i=2;
    afis[1]=v[mmaxim];
    while(prec[mmaxim]) afis[i++]=v[prec[mmaxim]], mmaxim=prec[mmaxim];
    for(j=i-1;j>=1;j--) g<<afis[j]<<' ';
	f.close();
	g.close();
	return 0;
}