Cod sursa(job #2129826)

Utilizator Vlad_NituNitu Vlad-Petru Vlad_Nitu Data 13 februarie 2018 09:55:54
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
long long n,i,a[100001],lmax,L[100001],Max,poz,nr,b[100001],j;
int main()
{
    f>>n;
    for(i=1; i<=n; i++)
        f>>a[i];
    L[1]=1;
    lmax=1;
    for(i=2; i<=n; i++)
    {
        Max=0;
        for(j=i-1; j>=1; j--)
            if(Max<L[j] && a[i]>a[j])
                Max=L[j];
        L[i]=1+Max;
        if(L[i]>lmax)
        {
            lmax=L[i];
            poz=i;
        }
    }
    nr=1;
    b[nr]=a[poz];
    lmax--;
    for(i=poz-1; i>=1; i--)
    {
        if(a[i]<b[nr] && L[i]==lmax)
        {
            nr++;
            b[nr]=a[i];
            lmax--;
        }
    }
    g<<nr<<endl;
    for(i=nr; i>=1; i--)
        g<<b[i]<<' ';

}