Cod sursa(job #1864366)

Utilizator IlluminatehPinzariu Denis Stefan Illuminateh Data 31 ianuarie 2017 18:43:24
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int N;

int v[100000], q[100000], t[100000];

void afisare(int ii)
{
    if(t[ii] > 0)
        afisare(t[ii]);

    out<<v[ii]<<' ';
}

int main()
{
    in>>N;

    int ii = 0;
    int maxim = -1000;



    for(int i=1;i<=N;i++)
    {

        in>>v[i];

        for(int j=1;j<i;j++)
            if(v[j] < v[i] && q[i] < q[j]+1)
            {
                q[i] = max(q[i], q[j]+1);
                t[i] = j;
            }

        if(q[i] > maxim)
        {
            maxim = q[i];
            ii = i;
        }


    }

    out<<maxim+1<<'\n';

    afisare(ii);


    return 0;
}