Cod sursa(job #2458662)

Utilizator andaraluca2001Anda Epure andaraluca2001 Data 21 septembrie 2019 11:58:15
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>

using namespace std;

//l[i]=liungimea celui mai lung subsir crescator care se termina pe pozitia i
//l[i]=1+max(l[j] cu proprietatile: o<j<i si v[j]<v[i]

/*

void subsir(int p)
{

    if(pred[p]) !=0)   subsir(pred[p]);

    out<<v[p];
    } +
     se apeleaza subsir (lmax)
     */



const int MAX=100006;
int a[MAX],n,l[MAX],imax,pred[MAX];

ifstream in("scmax.in");
ofstream out("scmax.out");

void sir(int ind,int l)
{
    if(l>1)
    {
        sir(pred[ind],l-1);
        out<<a[ind]<<" ";
        return;

    }

    if(l==1)
    {
         out<<a[ind]<<" ";
         return;

    }


}
int main()
{
    in>>n;

    for(int i=1;i<=n;i++)
    {
       in>>a[i];
       l[i]=1;
       }



    imax=1;
    for(int i=1;i<=n;i++)
    {
       for(int j=1;j<i;j++)
       {
          if(a[j]<a[i] && l[j]+1>l[i])
          {
              l[i]=l[j]+1;
              pred[i]=j;
          }

       }

       if(l[i]>l[imax]) imax=i;
    }

    out<<l[imax]<<"\n";


    sir(imax,l[imax]);




    return 0;
}