Cod sursa(job #2321008)

Utilizator Seba951Sebastian Boerescu Seba951 Data 15 ianuarie 2019 16:12:19
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>

using namespace std;

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

const int N=100001;
int n, maxi=-1, ok, maxi1=-1, ib;
int v[N], lung[N], pred[N], sol[N];

void citire()
{
    in>>n;
    for(int i=1; i<=n; i++) in>>v[i];
}

void verif(int i)
{
    for(int j=1; j<i; j++)
    {
        if(v[j]<v[i])
        {
            ok=1;
            if(v[j]>maxi)
            {
                lung[i]=lung[j]+1;
                pred[i]=j;
                maxi=v[j];
            }
        }
    }
    if(ok==0) lung[i]=1;
    ok=0;
    maxi=-1;
}

int main()
{
    citire();
    for(int i=1; i<=n; i++) verif(i);
    for(int i=1; i<=n; i++)
    {
        if(lung[i]>maxi1)
        {
            maxi1=lung[i];
            ib=i;
        }
    }
    int l=lung[ib];
    out<<l<<'\n';
    for(int i=1; i<=l; i++)
    {
        sol[i]=v[ib];
        ib=pred[ib];
    }
    for(int i=l; i>=1; i--) out<<sol[i]<<" ";
    return 0;
}