Cod sursa(job #2236376)

Utilizator TRIST0248SASASASA TRIST0248 Data 29 august 2018 12:36:36
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;
// Algorithm : subsir maxim crescator
set < int > tab;
int val[100001];
map <int,int> len;
vector <int> rez;
ifstream fin ("scmax.in");
ofstream fout("scmax.out");
int main()
{
    int n;
    fin >> n;
    int a;
    tab.insert(0);
    len[0] = 0;
    int  ml = 0;
    int  m = 0;
    for(int i = 1 ; i <= n ; i++){
        fin >> a;
        if(find(tab.begin(),tab.end(),a) == tab.end()){
        tab.insert(a);}
        set <int>::iterator pred = find(tab.begin(),tab.end(),a);
        pred -- ;
        //cout << *pred << endl;
        int lenght = len[*pred] + 1;
        if(lenght > ml){
            ml = lenght;
            m = a;
        }
        len[a] = lenght;
        val[a] = *pred;
    }
    fout << ml << endl;
    while(m > 0 ){
        rez.push_back(m);
        m = val[m] ;
    }
    for(int i = rez.size() - 1 ; i >= 0 ; i-- ){
        fout << rez[i] << " ";
    }
    return 0;
}