Cod sursa(job #3220429)

Utilizator AlexandruTigauTigau Alexandru AlexandruTigau Data 3 aprilie 2024 16:52:36
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int pre[100001], v[100001], lc[100001];
void reconstruire(int in)
{
    if(pre[in]!=0)
        reconstruire(pre[in]);
    g<<v[in]<<" ";
}
int main()
{
    int n,lmax=0,in;
    f>>n;
    for(int i=1;i<=100000;i++)
        lc[i]=1;
    for(int i=1;i<=n;i++)
    {
        f>>v[i];
        for(int j=i-1;j>=1;j--)
        {
            if(lc[j]+1==lc[i]&&v[j]<v[pre[i]])
                pre[i]=j;
            if(lc[j]+1>lc[i]&&v[j]<v[i])
                pre[i]=j, lc[i]=lc[j]+1;
        }
        if(lc[i]>lmax)
            lmax=lc[i], in=i;
    }
    g<<lmax<<'\n';
    reconstruire(in);
    return 0;
}