Cod sursa(job #2458655)

Utilizator andaraluca2001Anda Epure andaraluca2001 Data 21 septembrie 2019 11:47:59
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 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]
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;
}