Cod sursa(job #1906259)

Utilizator andrei_uAndrei andrei_u Data 6 martie 2017 12:58:05
Problema Subsir crescator maximal Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");

int n,i,j,a[100005],dp[100005],pre[100005],sol[100005],k,poz,nsol;
int main()
{
    cin>>n;
    for(i=1;i<=n;++i)
        cin>>a[i];

    dp[1]=1;
    for(i=2;i<=n;++i)
    {
        dp[i]=1;

        for(j=1;j<i;++j)
        {
            if(a[i]>a[j]) dp[i]=max(dp[i], 1+dp[j]), pre[i]=j;

        }
    }

    for(i=1;i<=n;++i)
    {
        if(dp[i]>k) {k=dp[i]; poz=i;}
    }


        cout<<k<<"\n";


    while(k>0)
    {

        sol[++nsol]=a[poz];
        poz=pre[poz];
        --k;

    }

    for(i=nsol;i>=1;--i) cout<<sol[i]<<" ";
    return 0;
}