Cod sursa(job #2457712)

Utilizator maramihaliMara Mihali maramihali Data 18 septembrie 2019 15:36:16
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX=100003;

int n, l[MAX],v[MAX],pre[MAX],pmax;

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

void subsir(int p)
{
    if(pre[p])
    {
        subsir(pre[p]);
    }
    out<<v[p]<<" ";
}

int main()
{
    in>>n;
    for(int i=1; i<=n; i++)
    {
        in>>v[i];
    }
    pmax = 1;
    for(int i=1; i<=n; i++)
    {
        int lc=0;
        for(int j=1; j<i; j++)
        {
            if(v[j]<v[i])
            {
                if(l[j]>lc)
                {
                    lc=l[j];
                    pre[i]=j;
                }
            }
        }
        l[i]=1+lc;
        if(l[i]>l[pmax])
        {
            pmax=i;
        }
    }
    out<<l[pmax]<<'\n';
    subsir(pmax);
    return 0;
}