Cod sursa(job #2173881)

Utilizator andreimuthMuth Andrei andreimuth Data 16 martie 2018 09:22:31
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#define nmax 100001
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scamx.out");

int i, n, a[nmax], lmax[nmax], pr[nmax], l, maxx, j, pred, start, k, sol[nmax];

int main()
{
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];
    lmax[1] = 1;
    for (i = 2; i <= n; i++)
    {
        l = 0;
        pred = 0;
        for (j = 1; j < i; j++)
        {
            if (a[j] < a[i] && lmax[j] > l)
                l = lmax[j], pred = j;
        }
        lmax[i] = 1 + l;
        pr[i] = pred;
    }

    maxx = 0;
    for (i = 1; i <= n; i++)
    {
        if (lmax[i] > maxx)
            maxx = lmax[i], start = i;
    }

    fout << maxx << '\n';
    while (pr[start] != 0)
    {
        sol[++k] = a[start];
        start = pr[start];
    }
    sol[++k] = a[start];

    for (i = k; i > 0; i--)
        fout << sol[i] << " ";


    return 0;
}