Cod sursa(job #1260070)

Utilizator bujorcatalin14Bujor Catalin bujorcatalin14 Data 10 noiembrie 2014 21:14:16
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n , a[100009];
int lg[100000];
int p[100000];
void Citire()
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++)
     fin>>a[i];
}
void Afisare(int n)
{
   if(p[n]!=0) Afisare(p[n]);
   fout<<a[n]<<" ";
}

void Generare()
{
    int i,j,max,pozmax;
    lg[1]=1;
    p[1]=0;
    for(i=2;i<=n;i++)
    {
        max=0; pozmax=0;
        for(j=1;j<i;j++)
         if(a[j]<a[i]&&lg[j]>max)
         {
             max=lg[j];
             pozmax=j;
         }
         lg[i]=max+1;
         p[i]=pozmax;
    }
    max=0; pozmax=0;
    for(i=1;i<=n;i++)
     if(lg[i]>max){max=lg[i]; pozmax=i;}
    fout<<max<<"\n";
     Afisare(pozmax);
}
int main()
{
    Citire();
   Generare();

    return 0;
}