Cod sursa(job #1789181)

Utilizator denisafrancuFrancu Denisa denisafrancu Data 26 octombrie 2016 19:20:44
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#define NMAX 100005
#include <fstream>

using namespace std;

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

int n, a[NMAX], l[NMAX],nr,pmax;

void citire()
{
    fin>>n;
    for(int i=0;i<n;i++)
        fin>>a[i];
}

int lg()
{
    pmax=n;
    for(int i=n-1;i>=0;i--)
    {
        l[i]=1;
        for(int j=i+1;j<n;j++)
            if(a[j]>a[i])
                l[i]=max(l[i],1+l[j]);
        if(l[i]>l[pmax])
            pmax=i;
    }
    return l[pmax];
}

void afisare()
{
    for(int i=pmax;i<n;)
    {
        gout<<a[i]<<" ";
        if(l[i]==1)
            break;
        for(int j=i+1;j<n;j++)
            if(a[j]>a[i] && l[j]==l[i]-1)
            {
                i=j;
                break;
            }

    }
}
int main()
{
    citire();
    gout<<lg()<<'\n';
    afisare();
    return 0;
}