Cod sursa(job #3224492)

Utilizator andreea_clapaClapa Andreea andreea_clapa Data 15 aprilie 2024 15:18:08
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <bits/stdc++.h>
#define N 100005

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int a[N],n,lmax[N],nx[N],st;
int main()
{
    fin>>n;
    for(int i=1; i<=n; ++i)
        fin>>a[i];
    lmax[n]=1;
    for(int i=n-1; i>=1; --i)
    {
        lmax[i]=1;
        for(int j=i+1; j<=n; ++j)
            if(a[i]<a[j]&&lmax[i]<lmax[j]+1)
                lmax[i]=lmax[j]+1;
    }
    int maxi=0;
    for(int i=1; i<=n; ++i)
        if(maxi<lmax[i]) maxi=lmax[i],st=i;
    fout<<maxi<<'\n'<<a[st]<<' ';
    for(int i=st+1;i<=n;++i)
        if(a[i]>a[st]&&lmax[i]==lmax[st]-1)
    {
        fout<<a[i]<<' ';
        st=i;
    }
    return 0;
}