Cod sursa(job #2143142)

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

using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
vector<long> sc;
int N;
int main()
{
    in>>N;
    long v[N];
    for(int i=0;i<N;++i)
        in>>v[i];
    long dp[N],cmax=1;
    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';
    if(1==cmax)
    {
        out<<v[0];
        return 0;
    }
    int l;
    for(int i=N-1;i>=0;--i)
        if(cmax==dp[i])
        {
            l=i;
            break;
        }
    long cont=v[l],coef=dp[l]-1;
    for(int i=l-1;i>=0;--i)
    {
        if(v[i]<cont && dp[i]==coef)
        {
            sc.push_back(v[i]);
            cont=v[i];
            --coef;
        }
        if(!coef)
            break;
    }
    while(!sc.empty())
    {
        out<<sc.back()<<' ';
        sc.pop_back();
    }
    out<<v[l];
    return 0;
}