Cod sursa(job #2165569)

Utilizator cezinatorCezar D cezinator Data 13 martie 2018 12:41:17
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int N,a[100005],L[100005],U[100005],lmax,poz;
int main()
{
    fin>>N;
    for(int i=1;i<=N;i++) {fin>> a[i];L[i]=1;}
    U[N]=0;
    for(int i=N-1;i>=1;i--)
    {
        {
            for(int j=i+1;j<=N;j++)
            {
                if(a[i]<a[j])
                {
                    if(L[i]<L[j]+1)
                    {
                        L[i]=L[j]+1;
                        U[i]=j;
                    }
                }
                else j=N;
            }
            if(lmax<L[i])
            {
                lmax=L[i];
                poz=i;
            }
        }
    }
    fout<<lmax<<'\n';
    while(U[poz]!=0) {fout<<a[poz]<<' ';poz=U[poz];}
    fout<<a[poz];
    return 0;
}