Cod sursa(job #2349419)

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