Cod sursa(job #2432645)

Utilizator KataIsache Catalina Kata Data 24 iunie 2019 16:34:28
Problema Subsir crescator maximal Scor 45
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int v[10002]; int lg[10002];
int main()
{
 int n,i,lgmax=0,j,st,dr,mijloc;
 fin>>n;
 for(i=1;i<=n;i++) fin>>v[i];
 for(i=0;i<=10001;i++) lg[i]=-1;
 for(i=1;i<=n;i++)
     {
       if(v[i]>lg[lgmax]) lg[++lgmax]=v[i];
       else {
             st=0;
             dr=lgmax+1;
            while (dr-st>1)
                  {mijloc=(st+dr)/2;
                   if (lg[mijloc]<v[i])
                       st=mijloc;
                   else dr=mijloc;
                   }
            lg[dr]=v[i];
                        }
     }
 fout<<lgmax<<'\n';
 for(i=1;i<=lgmax;i++) fout<<lg[i]<<" ";
 return 0;
}