Cod sursa(job #3314125)

Utilizator ilincaSSirbu Ilinca-Maria eu ilincaS Data 8 octombrie 2025 15:19:00
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <vector>

using namespace std;

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

int v[100005];
int f[100005];
int tr[100005];

vector <int> rez;

int main()
{
    int n, mx=0, cj;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
    }
    for(int i=1; i<=n; i++)
    {
        cj=mx=0;
        for(int j=i-1; j>=0; j--)
        {
            if(v[j]<v[i])
            {
                if(mx<f[j])
                {
                    mx=f[j];
                    cj=j;
                }
            }
        }
        if(mx+1>=f[i-1])
        {
            tr[i]=cj;
            f[i]=mx+1;
        }
        else
        {
            f[i]=f[i-1];
            tr[i]=tr[i-1];
        }
    }
    cout<<f[n]<<'\n';
    int poz=n;
    while(poz>0)
    {
        rez.push_back(v[poz]);
        poz=tr[poz];
    }
    for(int i=rez.size()-1; i>=0; i--)
    {
        cout<<rez[i]<<" ";
    }


    return 0;
}