Cod sursa(job #2349409)

Utilizator bogdan2604Bogdan Dumitrescu bogdan2604 Data 20 februarie 2019 14:15:46
Problema Subsir crescator maximal Scor 45
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <stack>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n,v[100000],emg[100000],i,d,mx,poz;
stack <int> stk;
int main()
{
    f>>n;
    for(i=0; i<n; ++i)
        f>>v[i],emg[i]=1;
    for(i=1; i<n; ++i)
        for(d=0; d<i; ++d)
            if(v[i]>v[d])
                emg[i]=max(emg[i],emg[d]+1);
    for(i=0; i<n; ++i)
        if(emg[i]>mx)
            mx=emg[i],poz=i;
    g<<mx<<'\n';
    stk.push(v[poz]);
    for(i=poz-1; i>=0&&mx; --i)
        if(v[i]<v[poz])
        {
            poz=i;
            stk.push(v[i]);
            --mx;
        }
    do
    {
        g<<stk.top()<<' ';
        stk.pop();
    }
    while(!stk.empty());
}