Cod sursa(job #1517738)

Utilizator LurchssLaurentiu Duma Lurchss Data 4 noiembrie 2015 19:11:26
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>

using namespace std;
int sir[100005],n;
int k[100005];
int subsir[100005];
int lmax,poz;
void citire()
{
 scanf("%d\n",&n);
 for(int i=1;i<=n;++i)
     scanf("%d\n",&sir[i]),k[i]=1;
}
void rez()
{
     for(int i=n;i>=1;--i)
        for(int j=i+1;j<=n;++j)
            if(sir[i]<sir[j] && k[i]<k[j]+1)
              k[i]=k[j]+1;
     for(int i=1;i<=n;i++)
        if(k[i]>lmax)
            lmax=k[i],poz=i;
        printf("%d\n",lmax);
}
void drum()
{
cout<<sir[poz]<<" ";
     for(int i=poz;i<=n;i++)
       if(lmax-1==k[i] && sir[i]>sir[poz])
           {
                poz=i;
                cout<<sir[i]<<" ";
                lmax--;
           }

}
int main()
{
   freopen("scmax.in","r",stdin);
   freopen("scmax.out","w",stdout);
   citire();
   rez();
   drum();
    return 0;
}