Cod sursa(job #3143648)

Utilizator stefan_arusteiiArustei Stefan stefan_arusteii Data 1 august 2023 11:09:47
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>
using namespace std;
short n, bst=1;
int num[1002], siz[1002];
ifstream in("sclm.in");
ofstream out("sclm.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;
        for(short j=i+1;j<=n;j++)
            if(num[i]<=num[j] && siz[i]<siz[j]+1)
                siz[i]=siz[j]+1;
    }

    //for(short i=1;i<=n;i++) cout<<siz[i]<<" ";

    // gasim primul element cu marimea maxima de subsir si afisez marimea
    for(short i=2;i<=n;i++) if(siz[i]>siz[bst]) bst=i;
    out<<siz[bst]<<"\n";

    //  folosim metoda backtracking pentru a gasi elementele subsirului cu marimea maxima si le afisam
    out<<num[bst];
    for(short i=bst+1;i<=n;i++)
    {
        if(siz[i]==siz[bst]-1)
        {
            if(num[i]>num[bst])
            {
                out<<" "<<num[i];
                bst=i;
            }
            else if(num[i]==num[bst]) bst=i;
        }
    }
    
    return 0;
}