Cod sursa(job #2553619)

Utilizator TudorChirila11Tudor Chirila TudorChirila11 Data 22 februarie 2020 10:30:56
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
const int N=100005;
int lg[N], a[N], urm[N], i, j, n, m,mx;
int main()
{
    fin>>n;
    for(i=1;i<=n;++i)
        fin>>a[i];
    lg[n]=1;urm[n]=0;
    for(i=n-1;i>=1;--i)
    {
        lg[i]=1;
        urm[i]=0;
        for(j=i+1;j<=n;++j)
            if(a[i]<a[j]&&lg[i]<1+lg[j])
        {
            lg[i]=lg[j]+1;
            urm[i]=j;
        }
    }
    for(i=1;i<=n;++i)
        if(mx<lg[i])
    {
        mx=lg[i];j=i;
    }
    fout<<lg[j]<<'\n';
    while(urm[j])
    {
        fout<<a[j]<<' ';
        j=urm[j];
    }
    fout<<a[j];
    return 0;
}