Cod sursa(job #2134243)

Utilizator sulzandreiandrei sulzandrei Data 17 februarie 2018 19:29:14
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
std::ifstream in("scmax.in");
std::ofstream out("scmax.out");

const int MAX_N =100000 +10;
int N;
int v[MAX_N]{0}, best[MAX_N]{0}, pind[MAX_N]{0};
int main()
{
    in >> N;
    for(int i =1 ; i <= N ; i++)
        in>>v[i], best[i] = 1, pind[i]=i;
    best[0] = 0;
    int bi;
    for(int i = 2 ; i <= N ; i++)
    {
        bi = 0;
        for(int j = 1 ; j< i ; j++)
            if(v[j]<v[i]&& best[j] > best[bi])
                bi = j;
        if(bi!=0)
        {
            best[i] = 1+best[bi];
            pind[i] = bi;
        }
    }
    int * el = max_element(best+1,best+1+N);
    int poz = 1;
    for(int i = 2 ; i <= N ; i++)
        if(best[i]>best[poz])
            poz = i;
    for(int i = *el ; i >=1 ; i--)
    {
        best[i] = v[poz];
        poz = pind[poz];
    }
    out<<*el<<'\n';
    for(int i = 1 ; i<= *el ; i++)
        out<<best[i]<<" ";

    return 0;
}