Cod sursa(job #1677804)

Utilizator coteanusebastianCoteanu coteanusebastian Data 6 aprilie 2016 19:59:35
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int v[100001],d[100001],i,n,j,t[100001],maxim,maxlength=0,poz,ok;
void rafis(int i)
{
    if(t[i])
    {
        rafis(t[i]);
    }
    g<<v[i]<<" ";
}
int main()
{   f>>n;
    d[0]=0;
    t[0]=0;
    for(i=1;i<=n;i++) f>>v[i];
    for(i=1;i<=n;i++)
    {
        j=i;
        maxim=0;
        ok=1;
        while(j>=1)
        {
            if(v[i]>v[j])
            {
                if(d[j]+1>maxim)
                {
                    d[i]=d[j]+1;
                    t[i]=j;
                    maxim=d[i];
                    ok=0;
                }
            }
            j--;
        }
        if(ok==1) d[i]=1;
        if(maxim>maxlength)
        {
            maxlength=maxim;
            poz=i;
        }
    }
    g<<maxlength<<'\n';
    rafis(poz);
    f.close();
    g.close();
    return 0;
}