Cod sursa(job #2884213)

Utilizator MateiDDumitrescu Matei Pavel MateiD Data 2 aprilie 2022 16:52:13
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int n,i,j,v[100005],l[100005],maxi,poz,last;
int main()
{
    fin>>n;
    ///l[i] = lungimea maxima a unui sir crescator care incepe cu elementul de pe pozitia i
    for(i=1;i<=n;i++)
    {
        fin>>v[i];
    }
    l[n]=1;
    for(i=n-1;i>=1;i--)
    {
        for(j=i+1;j<=n;j++)
        {
            if(v[i]<v[j]) l[i]=max(l[i],l[j]+1);
        }
    }
    for(i=1;i<=n;i++)
    {
        if(l[i]>maxi)
        {
            maxi=l[i];
            poz=i;
        }
    }
    fout<<maxi<<'\n';
    fout<<v[poz]<<' ';last=v[poz];
    maxi--;
    for(i=poz;i<=n;i++)
    {
        if(l[i]==maxi and last<v[i])
        {
            fout<<v[i]<<' ';
            maxi--;
            l[i]=last;
        }
    }
    return 0;
}