Cod sursa(job #2133719)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 17 februarie 2018 11:06:26
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

istream & in = fin;
ostream & out = fout;

int veclen;
int vec[100041];
int val[100041];

int maxi = 0;

void read()
{
    in >> veclen;
    for(int i = 0; i < veclen; i++){
        in >> vec[i];
    }
}

void solve()
{
    int maxp;
    for(int i = veclen - 1; i >= 0; i--){
        maxp = i;
        for(int j = i + 1; j < veclen; j++){
            if(vec[j] > vec[i] && val[j] > val[maxp]){
                maxp = j;
            }
        }
        val[i] = val[maxp] + 1;
        maxi = max(maxi, val[i]);
    }
}

void write()
{
    out << maxi << "\n";
    int aux = maxi, last = -1;
    for(int i = 0; i < veclen && aux > 0; i++){
        if(val[i] == aux && vec[i] > last){
            out << vec[i] << " ";
            last = vec[i];
            aux--;
        }
    }
}

int main()
{
    read();
    solve();
    write();
    return 0;
}