Cod sursa(job #2494829)

Utilizator Andrei_KeriAndrei Andrei_Keri Data 18 noiembrie 2019 15:47:14
Problema Subsir crescator maximal Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int V[100005];
int lg[100005];
int X[10000];
int main()
{
    int n,i,j,k=0,maxx,q,z;
    f>>n;
    for(i=1;i<=n;i++)
    f>>V[i];

    lg[n]=1;  k=1; maxx=n; q=1;
    for(i=n-1;i>=1;i--)
        {
        if(V[i]<maxx)
            {
            lg[i]=1+k;
            k=lg[i];
            maxx=V[i];
            }
        else
        {q=0;
            for(j=i+1;j<=n;j++)
            {
            if(V[i]<V[j])
                {
                if(lg[j]>q)
                    q=lg[j];
                }
            }
        lg[i]=q+1;
        if(lg[i]>k)
            {k=lg[i];
            maxx=V[i];
            }
        }
        }
    // lg este vector in care sunt lungimile ,k e lg max
    g<<k<<"\n";
    for(i=1;i<=n;i++)
    if(lg[i]==k)
        {
        break;
        }
    z=i;
    int a=V[z];
    q=k-1;
    g<<lg[z]<<" ";
    for(i=k+1;i<=n;i++)
        {
        if(q==0) break;
        if(lg[i]==q && a<V[i])
            {
            q--;
            a=V[i];
            g<<V[i]<<" ";
            if(q==0) break;
            }
        }
}