Cod sursa(job #2134222)

Utilizator sulzandreiandrei sulzandrei Data 17 februarie 2018 19:11:44
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <limits>
#define pb push_back
using namespace std;
std::ifstream in("scmax.in");
std::ofstream out("scmax.out");

const int MAX_N =100000;
int v[MAX_N+10]{0};
int N;
int best[MAX_N+10]{0};
int pind[MAX_N+10]{0};

// best i = 1 + best j unde 1<= j < i si A j < A i
// daca i e pozitia unui element din scmax atunci pind[i] e pozitia elementului precedent

int main()
{
    in >> N;
    for(int i =1 ; i <= N ; i++)
        in>>v[i];
    best[0] = 0;
    pind[0] = 0;
    for(int i = 1 ; i<= N ; i++)
        best[i] = 1, pind[i] = i;
    int bi;
    for(int i = 1 ; i <= N ; i++)
    {
        bi = 0;
        for(int j = 1 ; j< i ; j++)
            if(v[j]<v[i])
                bi = j;
        if(bi!=0)
        {
            best[i] = 1+best[bi];
            pind[i] = bi;
        }

    }
    int * el = max_element(best+1,best+1+N);
    out<<*el<<'\n';
    int poz = 1;
    for(int i = 2 ; i <= N ; i++)
        if(best[i]>best[poz])
            poz = i;
    vector<int> sorted;

    while(pind[poz]!=poz)

    {
        sorted.push_back(v[poz]);
        poz = pind[poz];
    }
    sorted.pb(v[poz]);
    for(auto it = sorted.rbegin(); it != sorted.rend() ; it++)
        out<<*it<<" ";

    return 0;
}