Cod sursa(job #1926304)

Utilizator murgoci1Gheorghe Murgoci murgoci1 Data 14 martie 2017 11:27:51
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>;
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
long long v[100001];
int l[100001],n,maxl,p,ok,maxx;
void afisare(int i)
{
    if(i>0)
    {
        int p = i;
        while(i>0&&!(v[i]<v[p]&&l[i]==l[p]-1))
            i--;
        afisare(i);
        fout<<v[p]<<" ";
    }


}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    l[1]=1;
    maxx=1;
    for(int i=2;i<=n;i++)
    {
        maxl=0;

        for(int j=i;j>=1&&maxl<maxx;j--)
        {
            if(v[i]>v[j])
            {
                if(l[j]>maxl)
                {
                    maxl=l[j];
                }

            }
        }
        l[i]=maxl+1;
        if(l[i]>maxx)
        {
                maxx=l[i];
                p=i;
        }
    }

    fout<<maxx<<'\n';
    afisare(p);
    return 0;
}