Cod sursa(job #1250887)

Utilizator sicsicFMI-Coteanu Vlad sicsic Data 28 octombrie 2014 18:22:17
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int v[100001],c[100001],d[100001],maxi=0,pmaxi=0,n;
void citire(int &n,int v[100001])
{
    f>>n;
    for(int i=1;i<=n;++i) f>>v[i];
}
void rafis(int pmaxi)
{
    if(c[pmaxi]==0) g<<v[pmaxi]<<" ";
    else {rafis(c[pmaxi]);
          g<<v[pmaxi]<<" ";
         }
}
void creare(int n,int v[100001])
{
    int i,j;
    for(i=1;i<=n;++i)
    {
        int poz=0;
        for(j=1;j<i;++j) if(v[j]<v[i]&&d[j]>d[poz]) poz=j;
        //g<<i<<" "<<poz<<'\n';
        if(poz)
        {
            d[i]=d[poz]+1;
            //d[poz]=0;
            c[i]=poz;
        }
        else
        {
            d[i]=1;
        }
        if(d[i]>maxi)
        {
            maxi=d[i];
            pmaxi=i;
        }
        //for(j=1;j<=n;++j) g<<v[j]<<" *"<<d[j]<<" *"<<c[j]<<'\n';
    }
   // for(i=1;i<=n;++i) g<<v[i]<<" "<<d[i]<<" "<<c[i]<<'\n';
   // g<<pmaxi<<'\n';
    g<<maxi<<'\n';
    rafis(pmaxi);
}
int main()
{
    citire(n,v);
    creare(n,v);
    g<<'\n';
    return 0;
}