Cod sursa(job #2721742)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 12 martie 2021 10:38:16
Problema Subsir crescator maximal Scor 45
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,i,ans,maxim,j,poz,nxt[100100],poz_ans,v[100100],L[100100];

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

    L[n]=1;
    for(i=n-1;i>=1;i--)
    {
        maxim=0;
        for(j=i+1;j<=n;j++)
        {
            if(v[j]>v[i] && L[j]>maxim)maxim=L[j],poz=j;
        }

        L[i]=maxim+1;
        nxt[i]=poz;

        if(L[i]>ans)ans=L[i],poz_ans=i;
    }

    g<<ans<<'\n';
    while(poz_ans!=0)
    {
        g<<v[poz_ans]<<" ";
        poz_ans=nxt[poz_ans];
    }
    return 0;
}