Cod sursa(job #2609669)

Utilizator Cristian25Cristian Stanciu Cristian25 Data 2 mai 2020 23:32:13
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>

using namespace std;

const char inputFile[] = "scmax.in";
const char outputFile[] = "scmax.out";

ifstream in(inputFile);
ofstream out(outputFile);

unsigned N, rez, pos;
vector<unsigned> v, dp;

void type(unsigned pos, unsigned rez)
{
    if(!rez)
        return;
    if(dp[pos] == rez)
    {
        if(pos > 0)
            type(pos - 1, rez - 1);
        out << v[pos] << ' ';
    }
    else type(pos - 1, rez);
}

int main(void)
{
    in >> N;
    v.resize(N);
    dp.resize(N);
    for(unsigned i = 0; i < N; ++i)
    {
        in >> v[i];
        dp[i] = 1;
        for(unsigned j = 0; j < i; ++j)
            if(v[j] < v[i] && dp[j] + 1 > dp[i])
            {
                bool ok = (dp[j] == rez);
                dp[i] = dp[j] + 1;
                if(dp[i] > rez)
                {
                    rez = dp[i];
                    pos = i;
                }
                if(ok)
                    goto end_loop;
            }
        end_loop:
        ;
    }
    out << rez << endl;
    type(pos, rez);
    return 0;
}