Cod sursa(job #2281354)

Utilizator Horea_Mihai_SilaghiHorea Mihai Silaghi Horea_Mihai_Silaghi Data 12 noiembrie 2018 08:37:48
Problema Subsir crescator maximal Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>

using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");
int n,v[100005],i,j,best[100005],pre[100005],lmax=0,pozmax,rez[100005],l=0;
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    best[1]=0;
    v[0]=-1;
    for(i=1;i<=n;i++)
    {
        for(j=i-1;j>=0;j--)
        {
            if(v[j]<v[i])
            {
                best[i]=best[j]+1;
                pre[i]=j;
                j=-1;
            }
        }
        if(best[i]>lmax)
        {
            lmax=best[i];
            pozmax=i;
        }
    }
    cout<<lmax<<endl;
    //for(i=1;i<=n;i++)
     //   cout<<v[i]<<" "<<best[i]<<" "<<pre[i]<<endl;
    l=lmax;
    i=pozmax;
    rez[l]=v[pozmax];
    l--;
    while(l)
    {
        rez[l]=v[pre[i]];
        i=pre[i];
        l--;
    }
    for(i=1;i<=lmax;i++)
        cout<<rez[i]<<" ";
    return 0;
}