Cod sursa(job #2113019)

Utilizator PTudorSergiuPilca Tudor Sergiu PTudorSergiu Data 24 ianuarie 2018 10:13:48
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <bits/stdc++.h>

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

int n,i,l[100001],urm[100001],a[100001],k,pmax;

int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>a[i];

    l[n]=1;
    urm[n]=n+1;
    pmax=n;
    for(i=n-1;i>0;i--)
    {
        l[i]=1;
        urm[i]=n+1;

        for(int k=i+1;k<=n;k++)
            if(a[i]<a[k])
                if(l[i]<l[k]+1)
                {
                    l[i]=l[k]+1;
                    urm[i]=k;
                    if(l[i]>l[pmax])
                        pmax=i;
                }
    }
    fout<<l[pmax]<<'\n';
    while(pmax<=n)
    {
        fout<<a[pmax]<<" ";
        pmax=urm[pmax];
    }
    return 0;
}