Cod sursa(job #2321018)

Utilizator vladstanciuVlad Stanciu vladstanciu Data 15 ianuarie 2019 16:22:39
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int N=100001;
int v[N],lung[N],pred[N],a[N];

void drum(int p)
{
    a[lung[p]-1]=v[pred[p]];
    if(lung[p]-1>0)
    {
    drum(pred[p]);
    }
}

int main()
{
    int n,i,ok,lungmax=0,pmax=0,j;
    in>>n;
    for(i=1 ; i<=n ; i++)
    {
        in>>v[i];
    }
    lung[1]=1;
    for(i=2 ; i<=n ; i++)
    {
        ok=0;
        for(j=1 ; j<i ; j++)
        {
            if(v[i]>v[j] && lung[i]<lung[j])
            {
                lung[i]=lung[j];
                pred[i] = j;
            }
        }
        lung[i]++;
        if(lung[i]>lungmax)
        {
            lungmax=lung[i];
            pmax=i;
        }
    }
    out<<lungmax<<"\n";
    a[lungmax]=v[pmax];
    drum(pmax);
    for(i=1 ; i<=lungmax ; i++)
    {
        out<<a[i]<<" ";
    }
    return 0;
}