Cod sursa(job #1962470)

Utilizator Marina23Oprea Marina Marina23 Data 11 aprilie 2017 19:55:57
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>

using namespace std;
int N,i,Lg[100001],A[100001],Maxitot,Caut,Ultim,Maxi,j,B[100001],k;
int main()
{
    ifstream fin("scmax.in");
    ofstream fout("scmax.out");

    fin>>N;
    for(i=1;i<=N;i++)
        fin>>A[i];
    Maxitot=-1;
    for(i=1;i<=N;i++)
    {
        Maxi=0;
        for(j=1;j<=i-1;j++)
            if(Lg[j]>Maxi and A[j]<A[i])
                Maxi=Lg[j];
        Lg[i]=Maxi+1;
        if(Lg[i]>Maxitot)
        {
            Maxitot=Lg[i];
            Ultim=A[i];
        }//if
    }//for i
    fout<<Maxitot<<'\n';
    B[1]=Ultim;
    Caut=Maxitot-1;
    k=1;
    while(Caut>=1)
    {
        for(i=1;i<=N;i++)
            if(Lg[i]==Caut and A[i]<Ultim)
            {
                k++;
                B[k]=A[i];
                Ultim=A[i];
                Caut--;
                break;
            }//if
    }//while
    for(i=k;i>=1;i--)
        fout<<B[i]<<" ";
    fin.close ();
    fout.close();
    return 0;
}