Cod sursa(job #2061624)

Utilizator andreichiricaAndrei Chirica andreichirica Data 9 noiembrie 2017 16:03:55
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>

using namespace std;

int main()
{
    int n,i,j,maxx,a[100005],Lmax,dp[100005],poz,p[100005],dim=0,rez[100005];
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    dp[1]=1;
    for(i=2;i<=n;i++)
    {
        Lmax=0;poz=0;
        for(j=1;j<i;j++)
            if(a[j]<a[i]&&Lmax<dp[j])
        {
            poz=j;
            Lmax=dp[j];
        }
    dp[i]=Lmax+1;
    p[i]=poz;
    }
    maxx=-1;poz=0;
    for(i=1;i<=n;i++)
        if(dp[i]>maxx)
    {
        maxx=dp[i];
        poz=i;
    }
    for(i=poz;i!=0;i=p[i])
    {
        dim++;
        rez[dim]=a[i];
    }
    cout<<dim;
    for(i=dim;i>=1;i--)
        cout<<rez[i]<<" ";
    return 0;
}