Cod sursa(job #1666305)

Utilizator narcios_neculaNarcis Necula narcios_necula Data 27 martie 2016 21:15:31
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n,i,mx,k,j,l[100001],t[100001],v[100001];
int main()
{
    f >> n;
    for(i = 1; i <= n; ++i)
        f >> v[i];
    l[n] = 1;
    t[n] = 0;
    for(i = n - 1; i >= 1; --i)
    {
        mx = 0;
        for(j = i + 1; j <= n; ++j)
            if(v[j] > v[i] && l[j] > mx)
            {
                mx = l[j];
                k = j;
            }
        t[i] = k;
        l[i] = mx + 1;
    }
    mx = 0;
    for(i = 1; i <= n; ++i)
        if(mx < l[i])
        {
            k = i;
            mx = l[i];
        }
    g << mx << '\n';
    while(mx > 0)
    {
        --mx;
        g << v[k] << " ";
        k = t[k];
    }
    g << '\n';
    return 0;
}