Cod sursa(job #3224484)

Utilizator andreea_clapaClapa Andreea andreea_clapa Data 15 aprilie 2024 15:08:37
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 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]; nx[i]=-1;}
    lmax[n]=1;
    for(int i=n-1;i>=1;--i)
        for(int j=i+1;j<=n;++j)
        if(a[i]<a[j]&&lmax[i]<lmax[j]+1)
        lmax[i]=lmax[j]+1,nx[i]=j;
    int maxi=0;
    for(int i=1;i<=n;++i)
        if(maxi<lmax[i]) maxi=lmax[i],st=i;
    fout<<maxi<<'\n';
    fout<<a[st]<<' ';
    while(nx[st]!=-1)
    {
        fout<<a[nx[st]]<<' ';
        st=nx[st];
    }
    return 0;
}