Cod sursa(job #2050402)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 28 octombrie 2017 09:47:35
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#define LM 100005
#define MAX(a,b) a>b?a:b
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");

int lgm[LM];
int urm[LM];

int n;
long long int a[LM];
int maxim;
int poz;

void af(int k);

int main()
{
    fin>>n;
    for (int i=1;i<=n;i++)
         fin>>a[i];
    lgm[n]=1;
    urm[n]=-1;
    for (int k=n-1;k>=1;k--)
        {
         maxim=-1;
         poz=-1;
         for (int i=k+1;i<=n;i++)
             if (a[k]<a[i]&&lgm[i]>maxim)
                 {
                  maxim=lgm[i];
                  poz=i;
                 }
         if (poz==-1)
            {
             urm[k]=-1;
             lgm[k]=1;
             continue;
            }
         urm[k]=poz;
         lgm[k]=maxim+1;
        }
    maxim=0;
    for (int i=1;i<=n;i++)
         maxim=MAX(lgm[i],maxim);
    fout<<maxim<<'\n';
    for (int i=1;i<=n;i++)
        if (lgm[i]==maxim)
        {
         af(i);
         break;
        }
    fin.close();
    fout.close();
    return 0;
}

void af(int k)
{
    if (lgm[k]==1) {fout<<a[k]<<'\n';return;}
    fout<<a[k]<<' ';
    af(urm[k]);
}