Cod sursa(job #3143653)

Utilizator stefan_arusteiiArustei Stefan stefan_arusteii Data 1 august 2023 11:26:45
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <deque>
using namespace std;
short n, bst=1;
int num[100002], siz[100002];
deque <int> elem[100002];
ifstream in("scmax.in");
ofstream out("scmax.out");
int main()
{
    // citesc toate elemantele
    in>>n;
    for(short i=1;i<=n;i++) in>>num[i];

    // generez lungime celui mai lung sir posibil pentru fiecare element
    siz[n]=1;
    for(short i=n-1;i>0;i--)
    {
        siz[i]=1;
        elem[i].push_back(i);
        for(short j=i+1;j<=n;j++)
            if(num[i]<num[j] && siz[i]<siz[j]+1)
            {
                siz[i]=siz[j]+1;
                elem[i].push_back(j);
            }
        if(siz[i]>siz[bst]) bst=i;
    }

    out<<siz[bst]<<"\n"<<num[bst]<<" ";
    while(!elem[bst].empty())
    {
        out<<num[elem[bst].front()]<<" ";
        elem[bst].pop_front();
    }
    
    return 0;
}