Cod sursa(job #2143096)

Utilizator Cristian25Cristian Stanciu Cristian25 Data 25 februarie 2018 16:23:42
Problema Subsir crescator maximal Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#define inf 2000000000

using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int N;
void Tipar(long v[],long cont,int pos)
{
    if(pos>=0)
    {
        if(v[pos]<cont)
        {
            Tipar(v,v[pos],pos-1);
            out<<v[pos]<<' ';
        }
        else Tipar(v,cont,pos-1);
    }
}
int main()
{
    in>>N;
    long v[N];
    for(int i=0;i<N;++i)
        in>>v[i];
    long dp[N],cmax=-inf;
    for(int i=0;i<N;++i)
    {
        dp[i]=1;
        for(int j=0;j<i;++j)
            if(v[i]>v[j])
            {
                dp[i]=max(1+dp[j],dp[i]);
                cmax=max(dp[i],cmax);
            }
    }
    out<<cmax<<'\n';
    int l=-1;
    for(int i=N-1;i>=0;--i)
        if(cmax==dp[i])
        {
            l=i;
            break;
        }
    Tipar(v,v[l],l-1);
    out<<v[l];
    return 0;
}