Cod sursa(job #2252059)

Utilizator PeraPera Alexandru Pera Data 2 octombrie 2018 11:51:36
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>

using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");
int n,i,j,v[100001],nr[100001],tt[100001],Max,poz,sol[100001],k;
int main()
{
    Max=0; poz=0;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i];
    for(i=1;i<=n;i++)
    {
        nr[i]=1; tt[1]=0;
        for(j=i-1;j>=1;j--)
        {
            if(v[i]>v[j])
                if(nr[i]<nr[j]+1)
            {
                nr[i]=nr[j]+1;
                tt[i]=j;
            }
        }
        if(nr[i]>Max)
        {
            Max=nr[i];
            poz=i;
        }
    }
    cout<<Max<<"\n";
    k=Max;
    while(k>0)
    {
        sol[k]=poz;
        poz=tt[poz];
        k--;
    }
    for(i=1;i<=Max;i++)
        cout<<v[sol[i]]<<" ";
    return 0;
}