Cod sursa(job #1649524)

Utilizator GeanaVladGeana Vlad GeanaVlad Data 11 martie 2016 13:59:11
Problema Subsir crescator maximal Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include<fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int v[100001],d[100001],n,i,j,mx,pmax,a[100001];
int main()
{
   f>>n;
   for(i=1;i<=n;i++) f>>v[i];
   for(i=1;i<=n;i++) d[i]=1;
   for(i=2;i<=n;i++)
   for(j=1;j<i;j++)
   {
       if(v[j]<v[i])
        {
            d[i]=max(d[i],d[j]+1);
            if(d[i]>mx) {pmax=i;mx=d[i];}
        }
   }
   g<<mx<<endl;
   i=mx;j=pmax;a[mx]=v[j];
   while(i>1)
   {
       if(d[j-1]==d[j]-1 && v[j-1]<v[j])
       {
           i--;
           j--;
           a[i]=v[j];
       }
       else j--;
   }
   for(j=1;j<=mx;j++) if(a[j]!=a[j-1]) g<<a[j]<<' ';
}