Cod sursa(job #2050386)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 28 octombrie 2017 09:44:22
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 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 next[LM];

int n;
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;
    next[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)
            {
             next[k]=-1;
             lgm[k]=1;
             continue;
            }
         next[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(next[k]);
}