Cod sursa(job #2193227)

Utilizator Stoica_TudorStoica Tudor Stoica_Tudor Data 9 aprilie 2018 13:29:20
Problema Subsir crescator maximal Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
//#include <iostream>
#include <fstream>
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");
int n,v[100002],h[100002],r[100002];

int main()
{
    int maxim=-1,indice=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    int minim=100000;
    for(int i=1;i<=n;i++)
    {
        if( v[i]<minim )
        {
            minim=v[i];
            h[i]=1;
            continue;
        }

        else
        {
            int maxi=-1;
            for(    int j=i-1; j>=1;   j--)
            {

                if( v[j] < v[i] )
                {
                    if( h[j]>maxi ) maxi=h[j];
                }
            }

               h[i]=maxi+1;
                if(  h[i]   > maxim)
                        maxim=h[i],indice=i;
        }
    }



int maxim2=maxim;

if(maxim==-1)
{
    cout<<1<<endl<<v[1];
}

else{
 cout<<maxim<<endl;

    for(   int j=n;  maxim2!=0 and j>=1;   j--)
 {
     if(    h[j]==maxim2   )
     {
         r[maxim2]=v[j];
         //r[maxim2]=j;
         maxim2--;
     }
 }
 for(int i=1;i<=maxim;i++)
 {
     cout<<r[i]<<" ";
 }

// for(int i=1;i<=n;i++)
// {
//     cout<<h[i]<<" ";
// }

}
    return 0;
}
/*
6
8 1 3 5 2 9

*/