Cod sursa(job #1927062)

Utilizator CammieCamelia Lazar Cammie Data 14 martie 2017 21:45:53
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>

#define MAXN 100005

using namespace std;

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

int n, lg[MAXN], pred[MAXN], v[MAXN];

inline void afisare(int nn)
{
    if (nn > 0)
    {
        afisare(pred[nn]);
        fout << v[nn] << " ";
    }
}

inline void Read()
{
    int pmax = 0;

    fin >> n;

    for (int i = 1; i <= n; i++)
    {
        fin >> v[i];

        lg[i] = 1;
        pred[i] = 0;

        for (int j = 1; j < i; j++)
        {
            if (v[j] < v[i] && lg[j] + 1 > lg[i])
            {
                lg[i] = lg[j] + 1;
                pred[i] = j;
            }
        }

        if (lg[pmax] < lg[i])
            pmax = i;
    }

    fout << lg[pmax] << "\n";
    afisare(pmax);
}

int main ()
{
    Read();

    fin.close(); fout.close(); return 0;
}