Cod sursa(job #2143081)

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

using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
vector<long> r;
int N;
int main()
{
    in>>N;
    long v[N];
    for(int i=0;i<N;++i)
        in>>v[i];
    int dp[N],start=-1,finish=-1,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';
    for(int i=N-1;i>=0;--i)
        if(cmax==dp[i])
        {
            for(int j=0;j<i;++j)
                if(v[j]<v[i])
                    r.push_back(v[j]);
            r.push_back(v[i]);
            break;
        }
    for(int i=0;i<r.size()-1;++i)
        if(r[i]<r[1+i])
        {
            out<<r[i]<<' ';
            if(i==r.size()-2)
                out<<r[1+i];
        }
    return 0;
}