Cod sursa(job #2607621)

Utilizator radu.damianDamian Radu radu.damian Data 29 aprilie 2020 22:14:01
Problema Subsir crescator maximal Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#define NMAX 100005
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n,v[NMAX],d[NMAX],val,x,sol[NMAX],cntr=0;
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    d[1]=1;
    for(int i=2;i<=n;i++)
     {
       for(int j=1;j<i;j++)
       {
           val=0;
           if(v[i]>v[j])
            val=1;
           if(d[j]+val>d[i])
             d[i]=d[j]+val;
       }
     }
     fout<<d[n]<<'\n';
     x=n;
     int i;
     while(i!=0)
     {
         for(i=x-1;i>=1;i--)
            if(d[x]==d[i]+1 && v[x]>v[i])
            {
                sol[++cntr]=v[x];
                x=i;
                break;
            }
         if(i==0)
         sol[++cntr]=v[x];
     }
     for(i=cntr;i>=1;i--)
        fout<<sol[i]<<' ';
     fout<<'\n';
    return 0;
}